QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233760 | #2704. Lexicographical Lecturing | Fyind | AC ✓ | 101ms | 52872kb | C++17 | 1.1kb | 2023-10-31 22:14:54 | 2023-10-31 22:14:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 500 + 5;
const int maxl = 2e4 + 5;
int n, m;
char s[maxn][maxl];
int L;
int lcp[maxn][maxl];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> L;
for (int i = 1;i <= n; ++i) {
for (int j = 1;j <= L; ++j) {
cin >> s[i][j];
}
}
for (int i = 1;i < n; ++i) {
int r = 0;
for (int l = 1;l <= L; ++l) {
r = max(r,l-1);
while (r+1 <= L && s[i][r+1] == s[i+1][r+1]) r++;
if (r == L || s[i][r+1] > s[i+1][r+1]) lcp[i][l] = INT_MAX/2;
else lcp[i][l] = r - l + 1;
}
}
int ans = L;
pii ansp = {1,L};
for (int l = 1;l <= L; ++l) {
int cur = 0;
for (int i = 1;i < n; ++i) {
cur = max(cur, lcp[i][l]+1);
}
if (cur < ans) {
ans = cur;
ansp = {l, l + cur - 1};
}
}
cout << ansp.first _ ansp.second << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5792kb
input:
2 1 a b
output:
1 1
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 7840kb
input:
26 1 a b c d e f g h i j k l m n o p q r s t u v w x y z
output:
1 1
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
4 2 aa ab ba bb
output:
1 2
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 7844kb
input:
25 2 aa ab ac ad ae ba bb bc bd be ca cb cc cd ce da db dc dd de ea eb ec ed ee
output:
1 2
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 51072kb
input:
484 2 aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av ba bb bc bd be bf bg bh bi bj bk bl bm bn bo bp bq br bs bt bu bv ca cb cc cd ce cf cg ch ci cj ck cl cm cn co cp cq cr cs ct cu cv da db dc dd de df dg dh di dj dk dl dm dn do dp dq dr ds dt du dv ea eb ec ed ee ef eg eh ei ej ...
output:
1 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 30344kb
input:
243 5 aaaaa aaaab aaaac aaaba aaabb aaabc aaaca aaacb aaacc aabaa aabab aabac aabba aabbb aabbc aabca aabcb aabcc aacaa aacab aacac aacba aacbb aacbc aacca aaccb aaccc abaaa abaab abaac ababa ababb ababc abaca abacb abacc abbaa abbab abbac abbba abbbb abbbc abbca abbcb abbcc abcaa abcab abcac abcba ...
output:
1 5
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 32412kb
input:
256 8 aaaaaaaa aaaaaaab aaaaaaba aaaaaabb aaaaabaa aaaaabab aaaaabba aaaaabbb aaaabaaa aaaabaab aaaababa aaaababb aaaabbaa aaaabbab aaaabbba aaaabbbb aaabaaaa aaabaaab aaabaaba aaabaabb aaababaa aaababab aaababba aaababbb aaabbaaa aaabbaab aaabbaba aaabbabb aaabbbaa aaabbbab aaabbbba aaabbbbb aabaaa...
output:
1 8
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 9856kb
input:
10 10 azzzzzzzzz bzzzzzzzzz czzzzzzzzz dzzzzzzzzz ezzzzzzzzz zzzzzzzzza zzzzzzzzzb zzzzzzzzzc zzzzzzzzzd zzzzzzzzze
output:
1 10
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
10 10 aababcbaca abacabbbac abacabcaaa baccbaaabb cbabbaacbb cbbaccaaca cbbbaaabcb cbbccaacaa cbcbbbccaa ccbcbcccaa
output:
1 7
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
10 10 aaaacaaacc aacbacabac bacbccacbb bbabccbbcb bbbbaacaac bbcbbacbac bccaabccaa cbccacccac ccaacbccbc ccbabacccb
output:
1 3
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
4 6 aaaaaa aaabbb aaacaa aaacac
output:
4 6
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
10 10 aacbaacaac abacabaabb acbaabcabc acbcacabac bcbbbaabbb caaababcba cbaabbacbb cbbbcbacbc cbcacbcccb cbcccccccc
output:
5 7
result:
ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
10 10 bccfawjqtl dbivwehcyz fvtdkthxop gajsvnggsq jumwfltycp oafdzbgdpz pnbtdsvaml uksdrbpzih xqqjewbwoo xsaxwciyvr
output:
1 2
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 9924kb
input:
10 10 bdqpbbsyed cfxhfklmhh etkqikpolw hmqrikxang lmicjowuoo okczjrgaou tbvpkkmeow uslalygxpx wubhnycnsm wyqhxznavk
output:
1 2
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
10 10 ckzcqbbdqa kizgvdefsw scshoejhgg tggibhkohf uqiookmtcs vmcrplrutp vvuuupsvmy wjouyqtwmt wkxxdrvygk wwkzszzyie
output:
6 6
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 15956kb
input:
100 100 aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...
output:
1 4
result:
ok
Test #17:
score: 0
Accepted
time: 3ms
memory: 16016kb
input:
100 100 aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...
output:
1 4
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 13952kb
input:
100 100 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa abababababababababababababababababababababababababababababababababababababababababababababababababab acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...
output:
1 2
result:
ok
Test #19:
score: 0
Accepted
time: 2ms
memory: 15992kb
input:
100 100 aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 100
result:
ok
Test #20:
score: 0
Accepted
time: 75ms
memory: 52100kb
input:
500 10000 aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...
output:
1 11
result:
ok
Test #21:
score: 0
Accepted
time: 75ms
memory: 52148kb
input:
500 10000 aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...
output:
1013 1022
result:
ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
3 5 cccca ccgda ccgia
output:
4 4
result:
ok
Test #23:
score: 0
Accepted
time: 72ms
memory: 51952kb
input:
500 10000 aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...
output:
1317 1326
result:
ok
Test #24:
score: 0
Accepted
time: 78ms
memory: 52144kb
input:
500 10000 aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...
output:
76 81
result:
ok
Test #25:
score: 0
Accepted
time: 77ms
memory: 52112kb
input:
500 10000 acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...
output:
1 4
result:
ok
Test #26:
score: 0
Accepted
time: 56ms
memory: 52108kb
input:
500 10000 aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...
output:
1 4
result:
ok
Test #27:
score: 0
Accepted
time: 73ms
memory: 52132kb
input:
500 10000 abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...
output:
1 4
result:
ok
Test #28:
score: 0
Accepted
time: 77ms
memory: 52108kb
input:
500 10000 abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...
output:
1 4
result:
ok
Test #29:
score: 0
Accepted
time: 46ms
memory: 52020kb
input:
500 10000 acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...
output:
1 2
result:
ok
Test #30:
score: 0
Accepted
time: 46ms
memory: 52120kb
input:
500 10000 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
9997 10000
result:
ok
Test #31:
score: 0
Accepted
time: 44ms
memory: 52160kb
input:
500 10000 aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 4
result:
ok
Test #32:
score: 0
Accepted
time: 45ms
memory: 52036kb
input:
500 10000 aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 10000
result:
ok
Test #33:
score: 0
Accepted
time: 49ms
memory: 51928kb
input:
500 10000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
6001 10000
result:
ok
Test #34:
score: 0
Accepted
time: 54ms
memory: 52004kb
input:
500 10000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
8189 10000
result:
ok
Test #35:
score: 0
Accepted
time: 86ms
memory: 52868kb
input:
500 20000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18001 20000
result:
ok
Test #36:
score: 0
Accepted
time: 101ms
memory: 52872kb
input:
500 20000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16381 20000
result:
ok