QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#189244#2704. Lexicographical LecturingBeevoAC ✓32ms54252kbC++201.1kb2023-09-27 03:21:482023-09-27 03:21:50

Judging History

This is the latest submission verdict.

  • [2023-09-27 03:21:50]
  • Judged
  • Verdict: AC
  • Time: 32ms
  • Memory: 54252kb
  • [2023-09-27 03:21:48]
  • Submitted

answer

#include <bits/stdc++.h>

#define el '\n'
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef long double ld;

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void testCase() {
    int n, l;
    cin >> n >> l;

    string s[n];
    for (int i = 0; i < n; i++)
        cin >> s[i];

    int dp[n][l];
    for (int i = 0; i + 1 < n; i++) {
        int sm = l;
        for (int j = l - 1; j >= 0; j--) {
            if (s[i][j] < s[i + 1][j])
                sm = j;
            else if (s[i][j] > s[i + 1][j])
                sm = l;

            dp[i][j] = sm;
        }
    }

    int a = 0, b = l - 1;
    for (int j = 0; j < l; j++) {
        int mx = 0;
        for (int i = 0; i + 1 < n; i++)
            mx = max(mx, dp[i][j]);

        if (mx != l && mx - j < b - a)
            a = j, b = mx;
    }

    cout << a + 1 << ' ' << b + 1;
}

signed main() {
    Beevo

    int t = 1;
//    cin >> t;

    while (t--)
        testCase();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3492kb

input:

2 1
a
b

output:

1 1

result:

ok 

Test #2:

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

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: 0ms
memory: 3492kb

input:

4 2
aa
ab
ba
bb

output:

1 2

result:

ok 

Test #4:

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

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: 3456kb

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: 1ms
memory: 3452kb

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: 1ms
memory: 3548kb

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: 0ms
memory: 3492kb

input:

10 10
azzzzzzzzz
bzzzzzzzzz
czzzzzzzzz
dzzzzzzzzz
ezzzzzzzzz
zzzzzzzzza
zzzzzzzzzb
zzzzzzzzzc
zzzzzzzzzd
zzzzzzzzze

output:

1 10

result:

ok 

Test #9:

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

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: 3488kb

input:

10 10
aaaacaaacc
aacbacabac
bacbccacbb
bbabccbbcb
bbbbaacaac
bbcbbacbac
bccaabccaa
cbccacccac
ccaacbccbc
ccbabacccb

output:

1 3

result:

ok 

Test #11:

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

input:

4 6
aaaaaa
aaabbb
aaacaa
aaacac

output:

4 6

result:

ok 

Test #12:

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

input:

10 10
aacbaacaac
abacabaabb
acbaabcabc
acbcacabac
bcbbbaabbb
caaababcba
cbaabbacbb
cbbbcbacbc
cbcacbcccb
cbcccccccc

output:

5 7

result:

ok 

Test #13:

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

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: 3528kb

input:

10 10
bdqpbbsyed
cfxhfklmhh
etkqikpolw
hmqrikxang
lmicjowuoo
okczjrgaou
tbvpkkmeow
uslalygxpx
wubhnycnsm
wyqhxznavk

output:

1 2

result:

ok 

Test #15:

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

input:

10 10
ckzcqbbdqa
kizgvdefsw
scshoejhgg
tggibhkohf
uqiookmtcs
vmcrplrutp
vvuuupsvmy
wjouyqtwmt
wkxxdrvygk
wwkzszzyie

output:

6 6

result:

ok 

Test #16:

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

input:

100 100
aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid
abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd
adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...

output:

1 4

result:

ok 

Test #17:

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

input:

100 100
aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec
aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha
abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...

output:

1 4

result:

ok 

Test #18:

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

input:

100 100
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abababababababababababababababababababababababababababababababababababababababababababababababababab
acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...

output:

1 2

result:

ok 

Test #19:

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

input:

100 100
aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 100

result:

ok 

Test #20:

score: 0
Accepted
time: 24ms
memory: 28776kb

input:

500 10000
aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...

output:

1 11

result:

ok 

Test #21:

score: 0
Accepted
time: 28ms
memory: 28908kb

input:

500 10000
aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...

output:

1013 1022

result:

ok 

Test #22:

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

input:

3 5
cccca
ccgda
ccgia

output:

4 4

result:

ok 

Test #23:

score: 0
Accepted
time: 23ms
memory: 28912kb

input:

500 10000
aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...

output:

1317 1326

result:

ok 

Test #24:

score: 0
Accepted
time: 20ms
memory: 28832kb

input:

500 10000
aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...

output:

76 81

result:

ok 

Test #25:

score: 0
Accepted
time: 32ms
memory: 28840kb

input:

500 10000
acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...

output:

1 4

result:

ok 

Test #26:

score: 0
Accepted
time: 32ms
memory: 28828kb

input:

500 10000
aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...

output:

1 4

result:

ok 

Test #27:

score: 0
Accepted
time: 24ms
memory: 28856kb

input:

500 10000
abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...

output:

1 4

result:

ok 

Test #28:

score: 0
Accepted
time: 27ms
memory: 28868kb

input:

500 10000
abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...

output:

1 4

result:

ok 

Test #29:

score: 0
Accepted
time: 8ms
memory: 28828kb

input:

500 10000
acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...

output:

1 2

result:

ok 

Test #30:

score: 0
Accepted
time: 12ms
memory: 28852kb

input:

500 10000
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

9997 10000

result:

ok 

Test #31:

score: 0
Accepted
time: 14ms
memory: 28840kb

input:

500 10000
aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 4

result:

ok 

Test #32:

score: 0
Accepted
time: 7ms
memory: 28816kb

input:

500 10000
aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 10000

result:

ok 

Test #33:

score: 0
Accepted
time: 8ms
memory: 28852kb

input:

500 10000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

6001 10000

result:

ok 

Test #34:

score: 0
Accepted
time: 15ms
memory: 28832kb

input:

500 10000
abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

8189 10000

result:

ok 

Test #35:

score: 0
Accepted
time: 30ms
memory: 54204kb

input:

500 20000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

18001 20000

result:

ok 

Test #36:

score: 0
Accepted
time: 20ms
memory: 54252kb

input:

500 20000
abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

16381 20000

result:

ok