QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233760#2704. Lexicographical LecturingFyindAC ✓101ms52872kbC++171.1kb2023-10-31 22:14:542023-10-31 22:14:55

Judging History

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

  • [2023-10-31 22:14:55]
  • 评测
  • 测评结果:AC
  • 用时:101ms
  • 内存:52872kb
  • [2023-10-31 22:14:54]
  • 提交

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