这个代码 WA 6 了,求大佬帮我调题,十分感谢:
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sort stable_sort
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
typedef double db;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}
ll quick_pow(ll a, ll b, const ll p) { if (b == 1) { return a * b % p;} if (b == 0) { return 1 % p;} ll x = quick_pow(a, b / 2, p); if (b & 1) { return (1ll * x * x % p * a) % p;} return (1ll * x * x) % p;}
const ll mod = 1e9 + 7;
// head
const int N = 201000, inf = 1e9;
int TC = 1, m;
struct Problem {
char id;
int firPen, secPen;
int firSub, lstSub;
int subCnt;
Problem(char _id = '\0') : id(_id), firPen(-1), secPen(-1), firSub(-1), subCnt(0) {}
void newSubmission(int t, bool ac) {
subCnt++;
lstSub = t;
if (firSub == -1)
firSub = t;
if (ac) {
int penalty = t + 20 * (subCnt - 1);
if (firPen == -1)
firPen = penalty;
else if (secPen == -1)
secPen = penalty;
}
}
int getPenalty() {
return firPen == -1 ? 0 : firPen;
}
int getScore() {
return firPen != -1;
}
int becomeWeak() {
return firPen == -1 ? 0 : (secPen == -1 ? inf - firPen : secPen - firPen);
}
int becomeStronger() {
return firPen == -1 ? inf - firPen : firPen - firSub;
}
int becomeAC() {
return firPen == -1 ? lstSub + 20 * (subCnt - 1) : -1;
}
};
vector<vector<Problem>> probs;
struct Team {
int id, score, penalty;
Team(int _id = -1) : id(_id), score(0), penalty(0) {}
void newSubmission(char tid, int t, bool ac) {
auto &prob = probs[id];
int pid = -1;
for (int i = 0; i < SZ(prob); i++)
if (prob[i].id == tid) {
pid = i;
break;
}
if (pid == -1) {
pid = SZ(prob);
prob.pb(tid);
}
score -= prob[pid].getScore();
penalty -= prob[pid].getPenalty();
prob[pid].newSubmission(t, ac);
score += prob[pid].getScore();
penalty += prob[pid].getPenalty();
}
void becomeWeak() {
auto &prob = probs[id];
int delta = 0;
for (auto p : prob)
delta = max(delta, p.becomeWeak());
if (delta >= inf / 2) {
score--;
penalty -= inf - delta;
}
else
penalty += delta;
}
void becomeStronger() {
auto &prob = probs[id];
int delta = 0;
for (auto p : prob)
delta = max(delta, p.becomeStronger());
if (delta >= inf / 2) {
score++;
penalty += inf - delta;
}
else
penalty -= delta;
}
void becomeAC() {
auto &prob = probs[id];
int delta = -1;
for (auto p : prob)
delta = max(delta, p.becomeAC());
if (delta >= 0) {
score++;
penalty += delta;
}
}
};
bool operator < (const Team &a, const Team &b) {
return (a.score != b.score) ? (a.score > b.score) : (a.penalty < b.penalty);
}
bool operator == (const Team &a, const Team &b) {
return a.score == b.score && a.penalty == b.penalty;
}
map<string, int> team_name;
vector<string> names;
vector<Team> teams;
int pos(string s) {
if (!team_name.count(s)) {
team_name[s] = SZ(team_name);
teams.pb(SZ(teams));
names.pb(s);
probs.pb({});
}
return team_name[s];
}
inline void solve() {
probs.clear();
teams.clear();
team_name.clear();
names.clear();
scanf("%d", &m);
for (int i = 0; i < m; i++) {
string name, result;
int time;
char problem;
cin >> name >> problem >> time >> result;
teams[pos(name)].newSubmission(problem, time, result == "accepted");
}
int teamCnt = SZ(teams), okTeam = 0;
for (auto team : teams)
okTeam += team.score >= 1;
int goldCnt = min(35, (okTeam + 9) / 10);
VI rank(teamCnt), canGold(teamCnt);
sort(all(teams));
for (int i = 0, j; i < teamCnt; i = j) {
j = i;
while (j < teamCnt && teams[i] == teams[j])
rank[j++] = i;
}
int hr = lower_bound(all(rank), goldCnt) - rank.begin();
for (int i = 0; i < hr; i++)
canGold[i] = 1;
if (min(35, (okTeam + 10) / 10) > goldCnt) {
int id = -1, rk = -1;
for (int i = 0; i < teamCnt; i++) {
if (teams[i].score >= 1)
continue;
auto getTeam = teams[i];
getTeam.becomeAC();
int getRank = lower_bound(all(teams), getTeam) - teams.begin();
if (getTeam.score >= 1 && rk < getRank) {
id = i;
rk = getRank;
}
}
if (id != -1) {
auto getTeam = teams[id];
getTeam.becomeAC();
for (int i = 0; i < teamCnt; i++) {
int newRank = rank[i] - (teams[id] < teams[i]) + (getTeam < teams[i]);
if (newRank < min(35, (okTeam + 10) / 10))
canGold[i] = 1;
}
}
}
for (int i = 0; i < goldCnt; i++) {
auto getTeam = teams[i];
getTeam.becomeWeak();
int newOkTeam = okTeam - (teams[i].score >= 1) + (getTeam.score >= 1);
int newGoldCnt = min(35, (newOkTeam + 9) / 10);
for (int j = hr; j < teamCnt; j++) {
int newRank = rank[j] - (teams[i] < teams[j]) + (getTeam < teams[j]);
if (newRank < newGoldCnt)
canGold[j] = 1;
}
}
for (int i = hr; i < teamCnt; i++) {
if (canGold[i])
continue;
auto getTeam = teams[i];
getTeam.becomeStronger();
int newOkTeam = okTeam - (teams[i].score >= 1) + (getTeam.score >= 1);
int newGoldCnt = min(35, (newOkTeam + 9) / 10);
int newRank = lower_bound(all(teams), getTeam) - teams.begin();
if (newRank < newGoldCnt)
canGold[i] = 1;
}
VI ans;
for (int i = 0; i < teamCnt; i++)
if (canGold[i])
ans.pb(i);
printf("%d\n", SZ(ans));
for (auto i : ans)
cout << names[teams[i].id] << " ";
puts("");
}
int main() {
scanf("%d", &TC);
while (TC--) {
solve();
}
}