QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#747098#6844. Suffix Automatonfrankly6RE 277ms129544kbC++171.8kb2024-11-14 16:20:152024-11-14 16:20:16

Judging History

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

  • [2024-11-14 16:20:16]
  • 评测
  • 测评结果:RE
  • 用时:277ms
  • 内存:129544kb
  • [2024-11-14 16:20:15]
  • 提交

answer

//求给定字符串的第 k 小字串(先比长度再比字典序), 问 1e6 次
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int MX=1000010;

int las=1, siz=1, cnt=-1;
PII rk[2*MX];
string s;
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
struct node{int s[26], f, len, id;}t[2*MX];
void ins(int c, int idx)
{
    int p=las, cur=++siz;
    t[cur].len=t[las].len+1;
    t[cur].id=idx;
    for(;p&&!t[p].s[c];p=t[p].f) t[p].s[c]=cur;
    if(!p) t[cur].f=1;
    else
    {
        int q=t[p].s[c];
        if(t[q].len==t[p].len+1) t[cur].f=q;
        else
        {
            int cl=++siz;
            t[cl]=t[q];
            t[cl].len=t[p].len+1;
            t[q].f=t[cur].f=cl;
            for(;p&&t[p].s[c]==q;p=t[p].f)
                t[p].s[c]=cl;
        }
    }
    las=cur;
}
queue<PII> q;
void bfs()
{
    q.push({1,0});
    while(!q.empty())
    {
        auto [u,dep]=q.front(); q.pop();
        rk[++cnt]={u,dep};
        for(int i=0;i<=25;i++)
            if(t[u].s[i]) q.push({t[u].s[i],dep+1});
    }
}
int main()
{
    // freopen("testdata.in","r",stdin);
    cin >> s;
    for(int i=0;i<s.size();i++) ins(s[i]-'a',i+1);
    bfs();
    int Q=read();
    while(Q--)
    {
        int rank=read();
        if(rank>cnt) cout << "-1 -1\n";
        else 
        {
            auto [id,dep]=rk[rank];
            cout << t[id].id-dep+1 << " " << t[id].id << '\n';
            // cout << "rank=" << rank << ", id=" << t[rk[rank]].id << '\n';
            // cout << t[rk[rank]].id-t[rk[rank]].len+1 << " " << t[rk[rank]].id << '\n';
        }
    }
    return (0-0);
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5616kb

input:

ccpcguilin
5
1
10
4
8
26

output:

1 1
2 3
8 8
1 2
4 7

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5648kb

input:

banana
3
5
10
16

output:

1 2
2 5
-1 -1

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 5632kb

input:

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
1000
752
397
968
637
706
758
780
574
1032
599
431
1038
700
868
252
1084
813
277
565
112
69
997
222
897
931
75
200
360
698
196
31
971
1064
591
485
179
528
71
45
422
272
925
8
197
796
116
187
983
1057
939
...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 69
-1 -1
-1 -1
-1 -1
-1 -1
1 75
-1 -1
-1 -1
-1 -1
-1 -1
1 31
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 71
1 45
-1 -1
-1 -1
-1 -1
1 8
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 5860kb

input:

ywyywywwywwywwwwwywwyyyywywywyyywywwywwwwwyyyyywwwwwwwywwwwwwwywyywwywwyyywwyyyyyyywyyyyyyywwy
1000
1545
1728
2068
3537
4585
3752
2495
3165
4342
4441
4109
4219
1709
3238
2946
1807
2717
4494
888
1956
1317
1508
3494
3945
3261
3892
1299
3903
2293
4055
218
3263
2265
793
4043
3851
2551
1478
1371
4015
267...

output:

26 50
17 44
32 64
30 94
-1 -1
8 81
51 91
19 73
-1 -1
-1 -1
-1 -1
-1 -1
52 79
10 66
10 59
9 37
8 52
-1 -1
44 59
44 74
47 68
35 59
20 83
1 87
4 60
9 90
41 62
12 94
27 63
-1 -1
4 11
26 82
56 92
24 38
-1 -1
6 84
39 80
28 51
19 41
-1 -1
17 60
59 89
40 56
22 56
-1 -1
62 78
57 84
27 49
12 17
11 32
56 82
34...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 5792kb

input:

pcfppcppppppffpppfffppfpfpffpfcffccffcfpcpfcfcfcppppfcppcccfffpffpfppffffcffffpfcpcpffppppff
1000
4871
1081
4356
3107
4567
4525
1585
3772
3802
3762
4827
3359
1004
511
4521
2924
4765
3146
2038
2652
3847
1381
1652
1000
4241
2288
4668
4396
4830
437
879
524
2346
4535
425
3738
2249
652
4865
1523
4014
303...

output:

-1 -1
30 46
-1 -1
20 70
-1 -1
-1 -1
54 77
11 82
19 92
13 84
-1 -1
34 91
30 45
59 68
-1 -1
18 64
-1 -1
25 76
58 88
51 91
11 86
47 67
2 26
6 21
-1 -1
54 88
-1 -1
-1 -1
-1 -1
43 51
1 14
73 82
48 83
-1 -1
35 43
18 88
23 56
22 32
-1 -1
53 75
-1 -1
26 74
27 88
35 84
72 84
9 83
1 83
-1 -1
1 27
60 77
31 47
...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 1ms
memory: 5576kb

input:

wejweujeuuweuweweuwwuwjwuuweeejwwujeeuujjeujjwwejejejwuewewuwjeejeejwuuwwuujuuueujeeueejuuu
1000
2184
2550
3992
3956
328
588
4911
3085
4725
974
4880
4674
2769
4546
662
4159
3161
3465
1310
2431
2018
4349
1057
919
767
3513
1844
3671
4385
3792
2031
180
1921
3576
3386
419
2162
3607
2108
308
1613
1681
20...

output:

11 42
15 53
-1 -1
4 90
42 48
82 91
-1 -1
39 88
-1 -1
67 81
-1 -1
-1 -1
38 80
-1 -1
8 18
-1 -1
3 54
14 73
70 88
50 86
50 79
-1 -1
12 27
23 36
34 45
23 84
49 75
17 84
-1 -1
11 83
62 91
23 27
6 33
13 76
6 63
56 63
53 84
1 65
39 69
46 51
33 55
54 77
24 52
55 62
45 73
44 57
9 84
43 75
23 58
18 79
5 63
5 ...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

wwhceznchkxaapvubwijfxcgyvqywqdoaizsoxlisttlszxwdhcrsmeznsfaldsnbwzxushrmcchhozkrasgnzpsvquthrrh
1000
3471
1192
980
2224
2431
3259
1439
2079
4858
931
3569
4572
1808
1651
1485
1346
3786
3803
2499
2748
5241
4136
1871
2465
1979
3027
264
4165
2885
4512
3061
4578
3724
5154
5258
289
3620
2197
505
4355
238...

output:

32 81
55 69
36 47
47 74
35 65
51 96
50 67
1 26
-1 -1
4 15
36 87
3 96
65 87
46 65
22 39
23 39
15 71
23 80
33 65
12 48
-1 -1
29 95
28 50
57 88
44 68
1 41
70 73
29 96
40 78
4 89
44 85
-1 -1
31 86
-1 -1
-1 -1
68 71
15 67
37 64
3 9
9 84
24 54
-1 -1
4 71
39 84
53 60
10 68
8 23
42 51
14 56
-1 -1
62 95
53 5...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 1ms
memory: 5648kb

input:

fylqobffxudwaqylowoinlqxzvrkswrmdjjnxymspxfxqkjccxzlrunqenyuvflyqfedfwyxrymuvmgmrazceolhdknvxldmk
1000
824
5124
1712
3832
570
3344
4775
3672
3208
4320
589
4098
1436
4177
4364
4664
3037
4456
5145
1425
2422
2973
2474
1175
2689
4978
463
4299
3826
2843
3948
2859
5378
2303
4565
1672
4641
397
4638
4514
11...

output:

61 70
-1 -1
65 85
36 92
24 30
24 69
-1 -1
10 62
3 46
9 79
89 96
17 80
13 30
15 80
17 89
4 96
35 75
19 95
-1 -1
50 66
63 93
43 82
62 93
72 85
5 39
-1 -1
60 65
6 76
16 72
59 95
22 81
34 71
-1 -1
14 42
14 96
25 44
7 96
25 29
9 97
17 96
37 50
36 94
52 81
9 35
53 58
18 50
-1 -1
32 86
40 55
26 33
-1 -1
35...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 7672kb

input:

pnbahlmruoyvhchfbmcpqfrypdbtbagydeldohigazreigkdauhhcvroajpdhfhiclppvtdcheqvuynvyfzujqklahtlftiklbo
1000
4143
5633
2928
1976
4140
5759
5507
3696
4895
2805
5641
3468
4547
4731
5391
802
548
1456
409
228
1221
2962
3931
4272
4060
1173
3633
3297
941
5302
2555
806
3891
5507
5118
2727
4831
2549
3178
2931
1...

output:

5 66
-1 -1
60 97
38 61
13 74
-1 -1
-1 -1
27 78
-1 -1
16 51
-1 -1
18 64
22 96
3 86
-1 -1
13 22
66 72
32 48
17 22
33 36
14 28
43 80
36 92
4 69
40 99
18 31
28 77
5 48
76 86
-1 -1
39 70
61 70
22 77
-1 -1
-1 -1
3 37
3 94
61 92
13 54
34 71
80 98
-1 -1
39 46
-1 -1
3 79
84 86
31 83
15 71
1 60
25 41
13 95
21...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 5636kb

input:

khnggceactpjxgkkgkmaaennymuudfchyfudhnehrzrwmarmcxeamtkdsrwphgebferyqdghqffxcxvjdcqyxxwrjv
1000
3149
4863
2912
3132
2464
3977
3823
3742
2382
4000
4307
2548
297
4495
2983
2030
3128
3329
1735
2643
3409
2207
376
3706
1305
918
2818
3092
3338
3527
3477
4102
581
560
450
1366
1157
3501
2638
2356
1205
3578
...

output:

23 71
-1 -1
37 80
5 53
3 37
8 89
16 86
24 90
51 84
3 86
-1 -1
7 43
56 60
-1 -1
13 57
61 88
39 87
30 83
27 49
42 79
12 67
22 52
9 14
14 79
67 83
73 84
40 81
17 64
12 65
8 67
12 69
-1 -1
15 22
65 72
84 89
26 43
57 71
7 65
44 81
41 73
2 17
3 63
38 58
51 74
17 88
4 75
58 82
27 28
39 73
77 82
-1 -1
1 2
-...

result:

ok 1000 lines

Test #11:

score: 0
Accepted
time: 257ms
memory: 129544kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 171154
1 828243
1 510784
1 804134
1 683819
1 326398
1 326368
1 906923
1 55858
1 800926
1 411361
1 584101
1 334671
1 321252
1 172896
1 139319
1 362552
1 881890
1 849611
1 724803
1 750804
1 670011
1 698097
1 77487
1 561441
1 144378
1 937646
1 917266
1 960579
1 704659
1 629076
1 872548
1 215439
1 237...

result:

ok 1000000 lines

Test #12:

score: 0
Accepted
time: 277ms
memory: 126240kb

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1 453459
1 325431
1 985403
1 22031
1 418936
1 962336
1 328894
1 886316
1 23532
1 621350
1 216413
1 652980
1 19591
1 789090
1 442931
1 74176
1 338246
1 516199
1 238878
1 227328
1 667551
1 958351
1 706926
1 956911
1 454973
1 459206
1 486441
1 360451
1 239082
1 61405
1 449730
1 516118
1 266368
1 492024...

result:

ok 1000000 lines

Test #13:

score: -100
Runtime Error

input:

ssqqqqqsssqqqsqsssqqsqsqsssqqsssssqqqqsqssssssqqqqqqqsqssqqsssssqssqqqqsqsqqqqsqsqsqqsqssqsqsqsqsqssqssqqssssqqsssqssssqqsqsqqsqsssqssssqsqqqsqqssssqssssqqsssssqqqqqqqsqqsqsssqssqsqsqssssqsqsqsssqqsqqqqqsssqqqqsssssssssqqsssssqqqssssqsssqqqsqqsqqqsssqqsqsqqqssqqqsqsssqqqsqsqsqsqqssssssqsqqqsqqsqsqsq...

output:


result: