QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#747098 | #6844. Suffix Automaton | frankly6 | RE | 277ms | 129544kb | C++17 | 1.8kb | 2024-11-14 16:20:15 | 2024-11-14 16:20:16 |
Judging History
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...