QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #356287 | #8230. Submissions | USTC_fish_touching_team# | WA | 170ms | 20332kb | C++14 | 5.9kb | 2024-03-17 17:18:03 | 2024-03-17 17:18:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define Re register int
#define ll long long
const int N = 100005, M = 2000005, Inf = 1e7;
struct info
{
int x, y;
}t, q[N];
int T, m, cnt, res, op, maxn, ans, ch[1000], hc[100], id[M], son[M][65], sol[N][30], sol1[N][30], sub[N][30], sub1[N][30], siz[N][30], siz1[N][30], tot[N], tim[N];
bool chk[N];
char s[30];
inline bool cmp(info x, info y)
{
return (x.x ^ y.x) ? x.x > y.x : x.y < y.y;
}
inline void dfs(int x, int y)
{
if (id[x] && chk[id[x]])
{
for (Re i = 1; i <= y; ++i) putchar(s[i]);
putchar(' ');
}
for (Re i = 0; i < 63; ++i)
{
if (!son[x][i]) continue;
s[y + 1] = hc[i];
dfs(son[x][i], y + 1);
}
}
int main()
{
scanf("%d", &T);
for (Re i = 0; i < 26; ++i) ch['a' + i] = i, hc[i] = 'a' + i;
for (Re i = 26; i < 52; ++i) ch['A' + i - 26] = i, hc[i] = 'A' + i - 26;
for (Re i = 52; i < 62; ++i) ch['0' + i - 52] = i, hc[i] = '0' + i - 52;
ch['_'] = 62, hc[62] = '_';
while (T--)
{
scanf("%d", &m);
cnt = 1, id[1] = res = op = maxn = ans = 0;
for (Re i = 0; i < 63; ++i) son[1][i] = 0;
for (Re i = 1; i <= m; ++i)
{
scanf("%s", s + 1);
int len = strlen(s + 1), now = 1;
for (Re j = 1; j <= len; ++j)
{
int u = ch[s[j]];
if (!son[now][u])
{
son[now][u] = ++cnt, id[cnt] = 0;
for (Re k = 0; k < 63; ++k) son[cnt][k] = 0;
}
now = son[now][u];
}
if (!id[now])
{
id[now] = ++res, tot[res] = tim[res] = chk[res] = 0;
for (Re j = 0; j < 26; ++j) sol[res][j] = sol1[res][j] = sub[res][j] = -1, siz[res][j] = siz1[res][j] = 0;
}
now = id[now];
char pr = getchar();
while (pr < 'A' || pr > 'Z') pr = getchar();
int u = pr - 'A', v, w;
scanf("%d", &v);
scanf("%s", s + 1);
w = (s[1] == 'a');
//printf("/*/*%d %d %d %d\n", now, u, v, w);
sub1[now][u] = v;
if (sol1[now][u] != -1) continue;
if (sub[now][u] == -1) sub[now][u] = v;
if (sol[now][u] == -1)
{
if (w) sol[now][u] = v, ++tot[now], tim[now] += v + 20 * siz[now][u], ++siz1[now][u];
else ++siz[now][u], ++siz1[now][u];
}
else
{
if (w) sol1[now][u] = v;
else ++siz1[now][u];
}
}
//for (Re i = 1; i <= res; ++i) printf("---%d %d %d\n", i, tot[i], tim[i]);
for (Re i = 1; i <= res; ++i)
if (tot[i]) q[++op] = (info){tot[i], tim[i]};
else
{
for (Re j = 0; j < 26; ++j)
if (sub[i][j] != -1) maxn = max(maxn, sub1[i][j] + 20 * (siz[i][j] - 1));
}
sort(q + 1, q + op + 1, cmp);
//printf("+%d\n", (op - 1) / 10 + 1);
//printf("++%d %d\n", q[1].x, q[1].y);
if (op) t = q[min((op - 1) / 10 + 1, 35)];
for (Re i = 1; i <= res; ++i)
{
if (!op) continue;
int u = min((op - 1) / 10 + 1, 35), v = min((op - 2) / 10 + 1, 35), u1, v1;
if (tot[i] > q[u].x || (tot[i] == q[u].x && tim[i] <= q[u].y))
{
//printf("**%d\n", i);
for (Re j = 0; j < 26; ++j)
if (sol[i][j] != -1)
{
if (sol1[i][j] == -1)
u1 = tot[i] - 1, v1 = tim[i] - (sol[i][j] + 20 * siz[i][j]);
else
u1 = tot[i], v1 = tim[i] - (sol1[i][j] - sol[i][j] + 20 * (siz1[i][j] - siz[i][j]));
if (!u1 && (op == 1 || u > v)) continue;
if (u1 < t.x || (u1 == t.x && v1 > t.y)) t = (info){u1, v1};
}
}
}
//printf("///%d\n", maxn);
//printf("!!%d %d\n", t.x, t.y);
for (Re i = 1; i <= res; ++i)
{
if (!op)
{
chk[i] = 1;
continue;
}
int u = min((op - 1) / 10 + 1, 35), v = min(op / 10 + 1, 35);
if (tot[i] > q[u].x || (tot[i] == q[u].x && tim[i] <= q[u].y))
{
chk[i] = 1;
continue;
}
int mn = Inf;
for (Re j = 0; j < 26; ++j)
if (sol[i][j] == -1 && sub[i][j] != -1) mn = min(mn, sub[i][j]);
if (mn < Inf)
{
if (!tot[i]) u = v;
if (u > op || (tot[i] + 1 > q[u].x || (tot[i] + 1 == q[u].x && tim[i] + mn <= q[u].y)))
{
chk[i] = 1;
continue;
}
}
else
{
mn = 0;
for (Re j = 0; j < 26; ++j)
if (sol[i][j] != -1) mn = max(mn, sol[i][j] + 20 * siz[i][j] - sub[i][j]);
if (tot[i] == q[u].x && tim[i] - mn <= q[u].y)
{
chk[i] = 1;
continue;
}
}
if (!tot[i]) continue;
if (tot[i] == q[u + 1].x && tim[i] == q[u + 1].y)
{
//printf("-%d\n", i);
if (u < v && op < res && (tot[i] > 1 || tim[i] <= maxn)) chk[i] = 1;
else if (tot[i] > t.x || (tot[i] == t.x && tim[i] <= t.y)) chk[i] = 1;
}
}
for (Re i = 1; i <= res; ++i) ans += chk[i];
printf("%d\n", ans);
dfs(1, 0);
putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 20328kb
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 ImYourFan LetItRot XuejunXinyoudui1
result:
ok 2 test cases ok. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 20308kb
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: 3ms
memory: 20192kb
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: 0ms
memory: 20332kb
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: 170ms
memory: 20304kb
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: 77ms
memory: 20260kb
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 fYuK1KNkuyO5HRCq tsd xiLm0TUOF3T Qua1Pti3vKhyQKDUm 2 t3 JP 2 fhYPGC8W82NwJTQL 77sgqpbTIr_Zt1 2 pVWDEz 3BQ 2 buCeoOotAkV8DaFD6 tg 1 UkXQ3iaNJ 2 vwfw ALTqPt7JUSLrl 1 QTEzV6tp 3 wJlbqIU 4e1l0pO8eFjZwkDo 9cy_y_RNRwex8j7224hz 2 eiuF7a_ 6mbCu5zA 1 xy6QBr8ECi 3 ldaKLZb1oS1sS PezeyUurYoz7N1iGU ...
result:
wrong answer the numbers are different in the case 487. (test case 487)