QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61023 | #2704. Lexicographical Lecturing | abdelrahman001 | AC ✓ | 69ms | 54660kb | C++20 | 1.5kb | 2022-11-09 06:17:20 | 2022-11-09 06:17:23 |
Judging History
answer
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 2e4 + 5;
const int M = 5e2 + 5;
int n, l, k[M][N];
string s[N];
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> l;
for(int i = 0;i < n;i++)
cin >> s[i];
for(int i = 1;i < n;i++) {
for(int j = 0;j < l;j++) {
int x = j;
while(x < l && s[i - 1][x] == s[i][x])
x++;
bool smaller = (s[i - 1][x] < s[i][x]);
for(int p = 0;p < min(l, x);p++)
k[i - 1][p] = x;
for(int p = x;p < l;p++) {
if(smaller == (s[i - 1][p] < s[i][p]))
k[i - 1][p] = p;
else {
int np = p;
while(np < l && s[i - 1][np] == s[i][np])
np++;
if(np == l) {
for(int pp = p;pp < np;pp++)
k[i - 1][pp] = 2e9;
break;
} else {
if((s[i - 1][np] < s[i][np]) == smaller) {
for(int pp = p;pp <= np;pp++)
k[i - 1][pp] = np;
} else {
for(int pp = p;pp <= np;pp++)
k[i - 1][pp] = 2e9;
}
p = np;
}
}
}
break;
}
}
int mn = 1e9, x, y;
for(int i = 0;i < l;i++) {
int mx = 0;
for(int j = 0;j + 1 < n;j++)
mx = max(mx, k[j][i]);
if(mx - i < mn)
mn = mx - i, x = i, y = mx;
}
cout << x + 1 << " " << y + 1;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5384kb
input:
2 1 a b
output:
1 1
result:
ok
Test #2:
score: 0
Accepted
time: 3ms
memory: 6092kb
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: 3ms
memory: 5408kb
input:
4 2 aa ab ba bb
output:
1 2
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 5948kb
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: 1ms
memory: 40872kb
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: 3ms
memory: 24228kb
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: 2ms
memory: 24044kb
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: 3ms
memory: 4040kb
input:
10 10 azzzzzzzzz bzzzzzzzzz czzzzzzzzz dzzzzzzzzz ezzzzzzzzz zzzzzzzzza zzzzzzzzzb zzzzzzzzzc zzzzzzzzzd zzzzzzzzze
output:
1 10
result:
ok
Test #9:
score: 0
Accepted
time: 2ms
memory: 3996kb
input:
10 10 aababcbaca abacabbbac abacabcaaa baccbaaabb cbabbaacbb cbbaccaaca cbbbaaabcb cbbccaacaa cbcbbbccaa ccbcbcccaa
output:
1 7
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 6092kb
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: 3940kb
input:
4 6 aaaaaa aaabbb aaacaa aaacac
output:
4 6
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 5792kb
input:
10 10 aacbaacaac abacabaabb acbaabcabc acbcacabac bcbbbaabbb caaababcba cbaabbacbb cbbbcbacbc cbcacbcccb cbcccccccc
output:
5 7
result:
ok
Test #13:
score: 0
Accepted
time: 2ms
memory: 6052kb
input:
10 10 bccfawjqtl dbivwehcyz fvtdkthxop gajsvnggsq jumwfltycp oafdzbgdpz pnbtdsvaml uksdrbpzih xqqjewbwoo xsaxwciyvr
output:
1 2
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 5988kb
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: 6132kb
input:
10 10 ckzcqbbdqa kizgvdefsw scshoejhgg tggibhkohf uqiookmtcs vmcrplrutp vvuuupsvmy wjouyqtwmt wkxxdrvygk wwkzszzyie
output:
6 6
result:
ok
Test #16:
score: 0
Accepted
time: 5ms
memory: 13536kb
input:
100 100 aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...
output:
1 4
result:
ok
Test #17:
score: 0
Accepted
time: 2ms
memory: 12256kb
input:
100 100 aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...
output:
1 4
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 13520kb
input:
100 100 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa abababababababababababababababababababababababababababababababababababababababababababababababababab acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...
output:
1 2
result:
ok
Test #19:
score: 0
Accepted
time: 5ms
memory: 12344kb
input:
100 100 aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 100
result:
ok
Test #20:
score: 0
Accepted
time: 63ms
memory: 47792kb
input:
500 10000 aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...
output:
1 11
result:
ok
Test #21:
score: 0
Accepted
time: 59ms
memory: 48640kb
input:
500 10000 aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...
output:
1013 1022
result:
ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 5540kb
input:
3 5 cccca ccgda ccgia
output:
4 4
result:
ok
Test #23:
score: 0
Accepted
time: 69ms
memory: 48984kb
input:
500 10000 aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...
output:
1317 1326
result:
ok
Test #24:
score: 0
Accepted
time: 54ms
memory: 48700kb
input:
500 10000 aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...
output:
76 81
result:
ok
Test #25:
score: 0
Accepted
time: 57ms
memory: 48900kb
input:
500 10000 acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...
output:
1 4
result:
ok
Test #26:
score: 0
Accepted
time: 38ms
memory: 47892kb
input:
500 10000 aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...
output:
1 4
result:
ok
Test #27:
score: 0
Accepted
time: 62ms
memory: 47848kb
input:
500 10000 abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...
output:
1 4
result:
ok
Test #28:
score: 0
Accepted
time: 58ms
memory: 48748kb
input:
500 10000 abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...
output:
1 4
result:
ok
Test #29:
score: 0
Accepted
time: 28ms
memory: 47792kb
input:
500 10000 acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...
output:
1 2
result:
ok
Test #30:
score: 0
Accepted
time: 17ms
memory: 48672kb
input:
500 10000 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
9997 10000
result:
ok
Test #31:
score: 0
Accepted
time: 24ms
memory: 48508kb
input:
500 10000 aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 4
result:
ok
Test #32:
score: 0
Accepted
time: 18ms
memory: 47772kb
input:
500 10000 aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 10000
result:
ok
Test #33:
score: 0
Accepted
time: 11ms
memory: 48560kb
input:
500 10000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
6001 10000
result:
ok
Test #34:
score: 0
Accepted
time: 5ms
memory: 48568kb
input:
500 10000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
8189 10000
result:
ok
Test #35:
score: 0
Accepted
time: 27ms
memory: 54596kb
input:
500 20000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18001 20000
result:
ok
Test #36:
score: 0
Accepted
time: 38ms
memory: 54660kb
input:
500 20000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16381 20000
result:
ok