QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #605457 | #8230. Submissions | DBsoleil# | WA | 5ms | 12744kb | C++20 | 4.5kb | 2024-10-02 17:19:34 | 2024-10-02 17:19:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1e5 + 5;
int n, m, tn, hn, tn1, sn, a[Maxn];
bool ans[Maxn];
map<string, int> ind;
string name[Maxn];
vector<pair<int, int>> v[Maxn][27], V[27];
int sum[Maxn], csum[Maxn][27], pend[Maxn], rsum, rcsum[27], rpend;
pair<int, int> grade[Maxn], rgrade[Maxn], tgrade[Maxn];
int get(const string &x) {
if (ind.find(x) == ind.end()) {
int t = (int)ind.size() + 1;
name[t] = x, ind[x] = t;
} return ind[x];
} // get
bool compare(pair<int, int> lhs, pair<int, int> rhs) {
return lhs.first > rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second);
} // compare
void calc(vector<pair<int, int>> *v, int &s, int c[], int &p) {
s = p = 0;
for (int j = 1; j <= 26; ++j) {
int cur_pend = 0; c[j] = 0;
for (const auto &[t, mn]: v[j]) {
// fprintf(stderr, "j = %d, (t, mn) = (%d, %d)\n", j, t, mn);
if (c[j] == 0) {
if (t == 0) cur_pend += 20;
else cur_pend += mn;
}
c[j] += t;
}
s += (c[j] > 0);
if (c[j] > 0) p += cur_pend;
}
} // calc
int main(void) {
cin.tie(nullptr)->sync_with_stdio(false);
int tests; cin >> tests;
while (tests--) {
ind.clear();
cin >> m;
for (int i = 0; i < m; ++i) {
string nm, ts, p; int mn;
cin >> nm >> ts >> mn >> p;
int j = get(nm), t = ts[0] - 'A' + 1;
v[j][t].emplace_back(p == "accepted", mn);
}
n = (int)ind.size(); hn = 0;
for (int i = 1; i <= n; ++i) {
calc(v[i], sum[i], csum[i], pend[i]);
grade[i] = {sum[i], pend[i]};
// fprintf(stderr, "grade[%d] = {%d, %d}\n", i, sum[i], pend[i]);
}
for (int i = 1; i <= n; ++i) hn += (sum[i] > 0);
if (hn == 0) {
for (int i = 1; i <= n; ++i) ans[i] = true;
} else {
tn = min((hn + 9) / 10, 35); sn = tn;
for (int i = 1; i <= n; ++i) a[i] = i;
sort(a + 1, a + n + 1, [&](int x, int y)->bool {
return compare(grade[x], grade[y]); });
while (sn + 1 <= n && grade[a[sn + 1]] == grade[a[sn]]) ++sn;
// fprintf(stderr, "sn = %d\n", sn);
// for (int i = 1; i <= n; ++i) fprintf(stderr, "a[%d] = %d\n", i, a[i]);
fill(ans + 1, ans + n + 1, false);
for (int i = 1; i <= sn; ++i) ans[a[i]] = true;
for (int i = tn + 1; i <= n; ++i) {
for (int j = 1; j <= 26; ++j) if (!v[a[i]][j].empty()) {
for (int k = 1; k <= 26; ++k) V[k] = v[a[i]][k];
for (auto &[p, mn]: V[j]) if (p == 0) { p = 1; break; }
calc(V, rsum, rcsum, rpend);
pair<int, int> rgrade = {rsum, rpend};
// if (i == 3) fprintf(stderr, "rgrade = {%d, %d}\n", rsum, rpend);
int hn1 = hn + (rsum != 0 && sum[a[i]] == 0);
int tn1 = min(35, (hn1 + 9) / 10);
// fprintf(stderr, "hn1 = %d, tn1 = %d\n", hn1, tn1);
if (compare(rgrade, grade[a[tn1]]) || rgrade == grade[a[tn1]]) { ans[a[i]] = true; break; }
}
}
if (sn == tn) {
for (int i = 1; i <= tn; ++i) {
for (int j = 1; j <= 26; ++j) if (!v[a[i]][j].empty()) {
for (int k = 1; k <= 26; ++k) V[k] = v[a[i]][k];
for (auto &[p, mn]: V[j]) if (p == 1) { p = 0; break; }
calc(V, rsum, rcsum, rpend);
pair<int, int> rgrade = {rsum, rpend};
int hn1 = hn - (rsum == 0);
int tn1 = min((hn1 + 9) / 10, 35);
if (tn1 != tn) continue;
if (compare(grade[a[tn1 + 1]], rgrade) || rgrade == grade[a[tn1 + 1]]) {
ans[a[tn1 + 1]] = true;
for (int s = tn1 + 2; s <= n && grade[a[s]] == grade[a[tn1 + 1]]; ++s)
ans[a[s]] = true;
break;
}
}
}
if (sum[a[n]] == 0) {
tn1 = min(hn / 10 + 1, 35);
if (tn1 != tn) {
int sn1 = tn1;
while (sn1 + 1 <= n && grade[a[sn1]] == grade[a[sn1 + 1]]) ++sn1;
for (int i = 1; i <= sn1; ++i) ans[a[i]] = true;
ans[a[tn1]] = true;
}
}
}
}
int nans = accumulate(ans + 1, ans + n + 1, 0);
cout << nans << endl;
vector<string> sans;
for (int i = 1; i <= n; ++i)
if (ans[i]) sans.push_back(name[i]);
for (int i = 0; i < (int)sans.size(); ++i)
cout << sans[i] << " \n"[i == (int)sans.size() - 1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= 26; ++j)
v[i][j].clear(), csum[i][j] = 0;
for (int i = 1; i <= n; ++i) sum[i] = pend[i] = 0;
}
return 0;
} // main
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 11832kb
input:
2 5 TSxingxing10 G 0 rejected TSxingxing10 B 83 accepted aoliaoligeiliao J 98 accepted TS1 J 118 accepted TS1 B 263 accepted 12 AllWayTheNorth A 0 rejected YaoYaoLingXian Y 10 accepted XuejunXinyoudui1 X 200 rejected XuejunXinyoudui1 X 200 accepted LetItRot L 215 accepted AllWayTheNorth W 250 accept...
output:
2 TSxingxing10 TS1 4 AllWayTheNorth XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 11864kb
input:
2 2 jiangly_fan A 1 accepted jiangly B 23 accepted 3 conqueror_of_tourist A 1 accepted conqueror_of_tourist A 2 accepted tourist B 23 accepted
output:
2 jiangly_fan jiangly 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 12744kb
input:
2 13 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 rejected 12 A A 1 accepted A X 1 accepted B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 a...
output:
11 A K B C D E F G H I J 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: -100
Wrong Answer
time: 5ms
memory: 11948kb
input:
2 11 A A 1 accepted B B 1 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 accepted H H 2 accepted I I 2 accepted J J 2 accepted K K 2 accepted 12 A A 1 accepted A X 1 accepted K K 1 rejected B B 2 accepted C C 2 accepted D D 2 accepted E E 2 accepted F F 2 accepted G G 2 a...
output:
2 A B 11 A K B C D E F G H I J
result:
wrong answer the numbers are different in the case 2. (test case 2)