QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #325186 | #8230. Submissions | ucup-team2000# | WA | 56ms | 4140kb | C++20 | 4.2kb | 2024-02-11 05:31:16 | 2024-02-11 05:31:16 |
Judging History
answer
#include <bits/stdc++.h>
std::vector<std::string> team_name;
int N, M;
char CC[110000][50];
int C[110000], P[110000];
int T[110000], S[110000];
std::vector<int> sub[110000][26];
std::pair<int, int> res[110000];
int ind[110000];
std::vector<int> ans;
std::pair<int, int> compute (int c, int p) {
int pp = 0;
for (int i = 0; i < (int) sub[c][p].size(); ++i) {
if (S[sub[c][p][i]] == 1) {
return {1, - pp - T[sub[c][p][i]]};
}
pp += 20;
}
return {0, 0};
}
int main() {
int TT; scanf("%d", &TT);
while (TT--) {
scanf(" %d", &M);
for (int i = 0; i < M; ++i) {
static char tmp[30];
scanf(" %s", CC[i]);
team_name.push_back(std::string(CC[i]));
scanf(" %s", tmp);
P[i] = tmp[0] - 'A';
scanf(" %d", &T[i]);
scanf(" %s", tmp);
if (tmp[0] == 'a') {
S[i] = 1;
} else {
S[i] = 0;
}
}
std::sort(team_name.begin(), team_name.end());
team_name.resize(std::unique(team_name.begin(), team_name.end()) - team_name.begin());
N = (int) team_name.size();
// for (int i = 0; i < N; ++i) printf("%s\n", team_name[i].c_str());
for (int i = 0; i < M; ++i) {
C[i] = std::lower_bound(team_name.begin(), team_name.end(), std::string(CC[i])) - team_name.begin();
// printf("%s\n", CC[i]);
}
for (int i = 0; i < M; ++i) {
sub[C[i]][P[i]].push_back(i);
}
for (int i = 0; i < N; ++i) {
int a = 0, b = 0;
for (int j = 0; j < 26; ++j) {
auto aa = compute(i, j);
a += aa.first;
b += aa.second;
}
res[i] = {a, b};
}
for (int i = 0; i < N; ++i) ind[i] = i;
std::sort(ind, ind + N, [&](int a, int b) { return res[a] > res[b]; });
int NN = 0;
for (int i = 0; i < N; ++i) NN += (res[i].first >= 1);
// printf("%d\n", NN);
int cutoff = std::min((NN + 9) / 10, 35);
auto cutoff1 = res[ind[cutoff - 1]];
std::pair<int, int> cutoffd = {-1E9, -1E9}, cutoff2 = {1E9, 1E9};
if (cutoff < N) cutoffd = res[ind[cutoff]];
// for (int i = 0; i < N; ++i) printf("%d %d\n", res[i].first, res[i].second);
// printf("%d %d %d %d\n", cutoff1.first, cutoff1.second, cutoff2.first, cutoff2.second);
for (int i = 0; i < cutoff; ++i) {
int ii = ind[i];
for (int j = 0; j < 26; ++j) {
auto aa = compute(ii, j);
if (aa.first == 1) {
int k = 0;
for (k = 0; k < (int) sub[ii][j].size(); ++k) if (S[sub[ii][j][k]] == 1) break;
S[sub[ii][j][k]] = 0;
auto bb = compute(ii, j);
S[sub[ii][j][k]] = 1;
auto ns = res[ii];
ns.first = ns.first - aa.first + bb.first;
ns.second = ns.second - aa.second + bb.second;
int newNN = NN;
if (ns.first == 0) --newNN;
int newcutoff = std::min((newNN + 9) / 10, 35);
if (newcutoff == cutoff) cutoff2 = std::min(cutoff2, std::max(cutoffd, ns));
}
}
}
// printf("%d %d %d %d\n", cutoff1.first, cutoff1.second, cutoff2.first, cutoff2.second);
int lstsub = -1;
{
int newNN = NN + 1;
int newcutoff = std::min((newNN + 9) / 10, 35);
if (newcutoff > cutoff && NN < N) {
for (int i = 0; i < N; ++i) {
if (res[i].first == 0) {
for (int j = 0; j < 26; ++j) {
if (!sub[i][j].empty()) {
lstsub = std::max(lstsub, T[sub[i][j].back()]);
}
}
}
}
}
}
for (int i = 0; i < N; ++i) {
int ii = ind[i];
if (res[ii] >= cutoff2) {
ans.push_back(ii);
} else {
if (lstsub != -1) {
if (res[ii] >= std::make_pair(1, -lstsub)) {
ans.push_back(ii);
continue;
}
}
{
for (int j = 0; j < 26; ++j) {
auto aa = compute(ii, j);
if (!sub[ii][j].empty()) {
int k = S[sub[ii][j][0]];
S[sub[ii][j][k]] = 1;
auto bb = compute(ii, j);
S[sub[ii][j][k]] = k;
auto ns = res[ii];
ns.first = ns.first - aa.first + bb.first;
ns.second = ns.second - aa.second + bb.second;
int newNN = NN;
if (res[ii].first == 0) ++newNN;
int newcutoff = std::min((newNN + 9) / 10, 35);
if (ns >= res[ind[newcutoff - 1]]) {
ans.push_back(ii);
break;
}
}
}
}
}
}
printf("%d\n", (int) ans.size());
for (int i = 0; i < (int) ans.size(); ++i) {
printf("%s%c", team_name[ans[i]].c_str(), " \n"[i + 1 == (int) ans.size()]);
}
ans.clear();
for (int i = 0; i < N; ++i) for (int j = 0; j < 26; ++j) sub[i][j].clear();
team_name.clear();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
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: 0ms
memory: 4128kb
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: 3ms
memory: 3844kb
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: 3ms
memory: 4140kb
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: 3928kb
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 4Vf5RXaTmySkFcXgHLOh 1...
result:
ok 100000 test cases ok. (100000 test cases)
Test #6:
score: -100
Wrong Answer
time: 51ms
memory: 3920kb
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...
output:
4 Qua1Pti3vKhyQKDUm fYuK1KNkuyO5HRCq xiLm0TUOF3T tsd 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 3BQ pVWDEz 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU _Yej1PrINty...
result:
wrong answer the numbers are different in the case 19. (test case 19)