QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #648986 | #8230. Submissions | xiaozhi | RE | 56ms | 8300kb | C++20 | 4.0kb | 2024-10-17 21:11:48 | 2024-10-17 21:11:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 2;
const int M = 26;
map<string, int> id;
string name[N];
array<vector<pair<int, string>>, M> g[N];
vector<array<int, 2>> rnk;
set<string> ans;
bool cmp(array<int, 2> &x, array<int, 2> &y) {
if (x[0] != y[0]) return x[0] > y[0];
return x[1] <= y[1];
}
void solve() {
int m;
cin >> m;
int n = 0;
for (int i = 1; i <= m; i++) {
string c, s;
char p;
int t;
cin >> c >> p >> t >> s;
int idx;
if (id.find(c) == id.end()) {
name[n] = c;
id[c] = n++;
}
idx = id[c];
g[idx][p - 'A'].push_back({t, s});
}
auto check = [&](int x) -> array<int, 2> {
array<int, 2> p1 = {0, 0};
for (int j = 0; j < M; j++) {
if (g[x][j].empty()) continue;
int fi = -1;
for (int k = 0; k < g[x][j].size(); k++) {
if (g[x][j][k].second == "accepted") {
fi = k;
break;
}
}
if (fi != -1) {
p1[0]++;
p1[1] += fi * 20 + g[x][j][fi].first;
}
}
return p1;
};
rnk.clear();
int h = 0;
for (int i = 0; i < n; i++) {
array<int, 2> p1 = check(i);
rnk.push_back(p1);
h += (p1[0] != 0);
}
sort(rnk.begin(), rnk.end(), [&](array<int, 2> &x, array<int, 2> &y) {
if (x[0] != y[0]) return x[0] > y[0];
return x[1] <= y[1];
});
int last = min((h + 9) / 10, 35), q;
for (int i = 0; i < n; i++) {
array<int, 2> p1 = check(i);
for (int j = 0; j < M; j++) {
if (g[i][j].empty()) continue;
int fi = -1, se = -1;
for (int k = 0; k < g[i][j].size(); k++) {
if (g[i][j][k].second == "accepted") {
if (fi == -1) {
fi = k;
} else {
se = k;
break;
}
}
}
if (fi == -1) {
h += (p1[0] == 0);
p1[0]++;
p1[1] += g[i][j][0].first;
q = min((h + 9) / 10, 35);
if (q == 0 || cmp(p1, rnk[q - 1])) ans.insert(name[i]);
p1[0]--;
p1[1] -= g[i][j][0].first;
h -= (p1[0] == 0);
} else {
p1[1] -= (20 * fi + g[i][j][fi].first - g[i][j][0].first);
q = min((h + 9) / 10, 35);
if (q > 0 && q - 1 < n && cmp(p1, rnk[q - 1])) ans.insert(name[i]);
p1[1] += (20 * fi + g[i][j][fi].first - g[i][j][0].first);
}
if (fi == -1 && p1[0] == 0) {
h++;
p1[0]++;
p1[1] += (g[i][j].size() - 1) * 20 + g[i][j].back().first;
q = min((h + 9) / 10, 35);
if (q > 0 && q - 1 < n && cmp(rnk[q - 1], p1)) last = max(last, q);
p1[0]--;
p1[1] -= ((g[i][j].size() - 1) * 20 + g[i][j].back().first);
h--;
}
q = min((h + 9) / 10, 35);
if (fi == -1 || q == 0 || !cmp(p1, rnk[q - 1])) continue;
if (se == -1) {
p1[0]--;
p1[1] -= (20 * fi + g[i][j][fi].first);
h -= (p1[0] == 0);
q = min((h + 9) / 10, 35);
if (q >= 0 && q < n && cmp(rnk[q], p1)) last = max(last, q + 1);
h += (p1[0] == 0);
p1[0]++;
p1[1] += (20 * fi + g[i][j][fi].first);
} else {
p1[1] += (20 * (se - fi) + g[i][j][se].first - g[i][j][fi].first);
q = min((h + 9) / 10, 35);
if (q >= 0 && q < n && cmp(rnk[q], p1)) last = max(last, q + 1);
p1[1] -= (20 * (se - fi) + g[i][j][se].first - g[i][j][fi].first);
}
}
}
for (int i = 0; i < n; i++) {
array<int, 2> p1 = check(i);
if (last > 0 && last - 1 < n && cmp(p1, rnk[last - 1])) ans.insert(name[i]);
}
cout << ans.size() << "\n";
for (auto ppp : ans) cout << ppp << " ";
cout << "\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < M; j++) g[i][j].clear();
}
id.clear();
ans.clear();
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(10);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 7052kb
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 TS1 TSxingxing10 4 AllWayTheNorth ImYourFan LetItRot XuejunXinyoudui1
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 2ms
memory: 8212kb
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 jiangly_fan 1 conqueror_of_tourist
result:
ok 2 test cases ok. (2 test cases)
Test #3:
score: 0
Accepted
time: 5ms
memory: 7496kb
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 B C D E F G H I J K 1 A
result:
ok 2 test cases ok. (2 test cases)
Test #4:
score: 0
Accepted
time: 2ms
memory: 8036kb
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 2 A K
result:
ok 2 test cases ok. (2 test cases)
Test #5:
score: 0
Accepted
time: 56ms
memory: 8300kb
input:
100000 1 M3JytWoaEXxkACy_mBAQ R 111 accepted 1 sQ O 151 accepted 1 JinbrcS58gNEE5yTSkT B 140 accepted 1 cklwBY V 243 accepted 1 v_o42YmvEKFwy Q 260 rejected 1 ftQVK8S_um22w K 265 accepted 1 _bQBeFeDpYQhvZcLf9l3 Z 147 accepted 1 KvDcEAIDN A 75 rejected 1 H3MUK6 A 101 rejected 1 gxYo_oCFn2J8aIben U 54...
output:
1 M3JytWoaEXxkACy_mBAQ 1 sQ 1 JinbrcS58gNEE5yTSkT 1 cklwBY 1 v_o42YmvEKFwy 1 ftQVK8S_um22w 1 _bQBeFeDpYQhvZcLf9l3 1 KvDcEAIDN 1 H3MUK6 1 gxYo_oCFn2J8aIben 1 _isnlUGK0ddI 1 BERcVjyCp 1 6In2do_50ylch 1 f0r3SXc6brMjT 1 7njYOapSwvogA 1 x 1 y1w3KvxylfxwprRBYw 1 aGedzS 1 iPo0GDhIF 1 4Vf...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: -100
Runtime Error
input:
10000 42 Bzs0PiQMXGZ5rRZ_2D G 2 accepted 9XtB_VIfbRRL E 11 accepted FVJL M 13 rejected a S 19 accepted tsd Z 20 rejected MyCqVEg1ONjZ U 22 accepted 6SgZMn N 51 rejected Qua1Pti3vKhyQKDUm P 54 accepted i29 M 63 accepted zPqu D 68 rejected xx2yiu6x C 71 rejected fYuK1KNkuyO5HRCq L 76 rejected tXWpYVqj...