QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356287#8230. SubmissionsUSTC_fish_touching_team#WA 170ms20332kbC++145.9kb2024-03-17 17:18:032024-03-17 17:18:03

Judging History

你现在查看的是最新测评结果

  • [2024-05-20 23:50:57]
  • hack成功,自动添加数据
  • (/hack/623)
  • [2024-05-20 23:48:44]
  • hack成功,自动添加数据
  • (/hack/622)
  • [2024-03-17 17:18:03]
  • 评测
  • 测评结果:WA
  • 用时:170ms
  • 内存:20332kb
  • [2024-03-17 17:18:03]
  • 提交

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;
}

详细

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)