QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #647415 | #8230. Submissions | AlphaZe | WA | 59ms | 72668kb | C++20 | 6.4kb | 2024-10-17 13:59:26 | 2024-10-17 13:59:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
const int M = 1e5 + 10, N = 25, inf = 0x3f3f3f3f;
const ll mod = 998244353, p = 13331;
int m, n;
int penal[26];
bool ans[M];
struct Submit {
int t, s;
};
struct Grade {
int nm, t;
void clear() { nm = t = 0; }
bool operator < (const Grade &that) const {
if (nm == that.nm) return t < that.t;
return nm > that.nm;
}
bool operator == (const Grade &that) const {
return nm == that.nm && t == that.t;
}
};
struct Team {
char str[N];
vector<Submit> e[26];
int ac;
Grade g1, g2, g3, g4, g5;
void ins() {
g1.clear(); memset(penal, 0, sizeof penal);
// puts("sb?1");
for (int i = 0; i < 26; ++i) {
if (ac >> i & 1) {
++g1.nm; // puts("sb?");
for (auto sub : e[i]) {
if (sub.s) {
g1.t += sub.t, penal[i] += sub.t;
break;
} else g1.t += 20, penal[i] += 20;
}
}
} // 初始成绩
g2 = g1;
for (int i = 0; i < 26; ++i) {
if (!(ac >> i & 1)) {
if (!e[i].empty()) {
Grade nowg = {g1.nm + 1, g1.t + e[i][0].t};
g2 = min(g2, nowg);
}
} else {
Grade nowg = {g1.nm, g1.t - penal[i] + e[i][0].t};
g2 = min(g2, nowg);
}
} // 改一个成绩后最优
g5.clear();
if (!g1.nm) {
g5.nm = 1;
for (int i = 0; i < 26; ++i) {
if (!e[i].empty())
g5.t = max(g5.t, e[i][e[i].size() - 1].t + (int)(e[i].size() - 1) * 20);
}
} // 没过题, 改一个成绩后最差
g3 = g4 = g1;
for (int i = 0; i < 26; ++i) {
if (ac >> i & 1) {
int nowpenal = 0, times = 0;
for (auto sub : e[i]) {
if (!sub.s) nowpenal += 20;
else {
if (!times) {
nowpenal += 20; ++times;
} else {
nowpenal += sub.t; ++times; break;
}
}
}
if (times == 1) g3 = max(g3, {g1.nm - 1, g1.t - penal[i]});
else g4 = max(g4, {g1.nm, g1.t - penal[i] + nowpenal});
}
} // g3为少过题的最差, g4为未少过题的最差.
}
bool operator < (const Team &that) const {
// if (g1 == that.g1) return max(that.g3, that.g4) < max(g3, g4);
return g1 < that.g1;
}
}nd[M];
int getgold(int x) {
if (x % 10 == 0) return min(x / 10, 35);
return min(x / 10 + 1, 35);
}
void work() {
m = read(); n = 0; map<ll, int> mp;
for (int i = 1; i <= m; ++i) {
char str[N];
scanf("%s", str + 1);
int len = strlen(str + 1); ll has = 0;
for (int j = 1; j <= len; ++j) has = (has * p + str[j]) % mod;
if (mp.find(has) == mp.end()) {
mp[has] = ++n;
for (int j = 1; j < N; ++j) nd[n].str[j] = str[j];
for (int j = 0; j < 26; ++j) nd[n].e[j].clear(); nd[n].ac = 0;
}
int idx = mp[has];
char problem = getchar();
while (problem < 'A' || problem > 'Z') problem = getchar();
int t = read();
char status = getchar();
while (status != 'r' && status != 'a') status = getchar();
int p = problem - 'A', s = status == 'a';
if (s == 1) nd[idx].ac |= 1 << p;
nd[idx].e[p].push_back({t, s});
// printf("nd[%d].e[%d].pb({%d, %d}); \n", idx, p, t, s);
while (status != '\n') status = getchar();
}
for (int i = 1; i <= n; ++i) {
nd[i].ins();
// printf("%s\n", nd[i].str + 1);
// printf("{%d, %d}, {%d, %d}, {%d, %d}, {%d, %d}; \n", nd[i].g1.nm, nd[i].g1.t, nd[i].g2.nm, nd[i].g2.t, nd[i].g3.nm, nd[i].g3.t, nd[i].g4.nm, nd[i].g4.t);
}
sort(nd + 1, nd + n + 1);
// for (int i = 1; i <= n; ++i) {
// printf("%s\n", nd[i].str + 1);
// printf("{%d, %d}, {%d, %d}, {%d, %d}, {%d, %d}; \n", nd[i].g1.nm, nd[i].g1.t, nd[i].g2.nm, nd[i].g2.t, nd[i].g3.nm, nd[i].g3.t, nd[i].g4.nm, nd[i].g4.t);
// }
int nn = n;
for (int i = nn; i; --i)
if (!nd[i].g1.nm) nn = i - 1;
else break;
int gold = getgold(nn);
// for (int i = gold + 1; i <= nn; ++i)
// if (nd[i].g1 == nd[gold].g1) ++gold;
for (int i = 1; i <= n; ++i) ans[i] = 0;
for (int i = 1; i <= gold; ++i) ans[i] = 1;
if (nn != n && getgold(nn) != getgold(nn + 1)) {
Grade tog = nd[nn + 1].g5;
for (int i = nn + 1; i <= n; ++i) tog = max(tog, nd[i].g5);
tog = min(tog, nd[gold + 1].g1);
// printf("tog = {%d, %d}; \n", tog.nm, tog.t);
for (int i = gold + 1; i <= nn; ++i) {
if (nd[i].g1 < tog || nd[i].g1 == tog) ans[i] = 1;
}
} // 金牌线扩充
for (int i = gold + 1; i <= n; ++i) {
int nown = nn + (nd[i].g1.nm == 0), nowgold = getgold(nown);
// printf("nown = %d, nowgold = %d; \n", nown, nowgold);
if (nd[i].g2 < nd[nowgold].g1 || nd[i].g2 == nd[nowgold].g1) ans[i] = 1;
} // 改自己最大
bool tag = 0;
if (getgold(nn) != getgold(nn - 1)) tag = 1;
Grade tog = nd[1].g4; int id = 1;
for (int i = 1; i <= gold; ++i) {
Grade nowtog = nd[i].g4;
if (nd[1].g3.nm || (!tag)) nowtog = max(nowtog, nd[i].g3);
if (tog < nowtog) tog = nowtog, id = i;
}
tog = min(tog, nd[gold + 1].g1);
// printf("tog = {%d, %d}; \n", tog.nm, tog.t);
for (int i = gold + 1; i <= n; ++i) {
if (nd[i].g1 < tog || nd[i].g1 == tog) ans[i] = 1;
}
int ansnm = 0;
for (int i = 1; i <= n; ++i) ansnm += ans[i];
printf("%d\n", ansnm);
for (int i = 1; i <= n; ++i)
if (ans[i]) printf("%s ", nd[i].str + 1); putchar('\n');
}
int main() {
int Tt = read();
while (Tt--) work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 72568kb
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 XuejunXinyoudui1 LetItRot ImYourFan
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 7ms
memory: 72596kb
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: 7ms
memory: 72640kb
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: 4ms
memory: 72560kb
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: 59ms
memory: 72512kb
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
Wrong Answer
time: 42ms
memory: 72668kb
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 pVWDEz 3BQ 2 tg buCeoOotAkV8DaFD6 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 9cy_y_RNRwex8j7224hz wJlbqIU 4e1l0pO8eFjZwkDo 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU ...
result:
wrong answer the numbers are different in the case 231. (test case 231)