QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188987#2704. Lexicographical LecturingIsaacMoris#AC ✓41ms54140kbC++171.3kb2023-09-26 18:35:402023-09-26 18:35:41

Judging History

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

  • [2023-09-26 18:35:41]
  • 评测
  • 测评结果:AC
  • 用时:41ms
  • 内存:54140kb
  • [2023-09-26 18:35:40]
  • 提交

answer

#include<iostream>
#include <bits/stdc++.h>

#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 500 + 5, inf = 2e9;

string s[N];
int go[N][20009];
int n, m;

void preprocess() {

    for (int i = 0; i + 1 < n; i++) {
        go[i][m] = m;
        for (int j = m - 1; j >= 0; j--) {
            if (s[i][j] != s[i + 1][j]) {
                go[i][j] = j;
            } else {
                go[i][j] = go[i][j + 1];
            }
        }
    }
}

int solve(int idx) {
    int r = 0;
    for (int i = 0; i + 1 < n; i++) {
        int nxt = go[i][idx];
        if (nxt == m || s[i][nxt] > s[i + 1][nxt]) return 1e9;
        r = max(r, nxt);
    }
    return r;
}

void doWork() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    preprocess();

    int l = 0, r = m - 1;
    for (int i = 0; i < m; i++) {
        int ans = solve(i);
        if (ans - i < r - l) {
            l = i;
            r = ans;
        }
    }
    cout << l + 1 << " " << r + 1;
}

int main() {
    IO
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}
 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 1
a
b

output:

1 1

result:

ok 

Test #2:

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

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

input:

4 2
aa
ab
ba
bb

output:

1 2

result:

ok 

Test #4:

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

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

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

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

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

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

input:

10 10
aababcbaca
abacabbbac
abacabcaaa
baccbaaabb
cbabbaacbb
cbbaccaaca
cbbbaaabcb
cbbccaacaa
cbcbbbccaa
ccbcbcccaa

output:

1 7

result:

ok 

Test #10:

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

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

input:

4 6
aaaaaa
aaabbb
aaacaa
aaacac

output:

4 6

result:

ok 

Test #12:

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

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

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

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

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

input:

100 100
aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid
abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd
adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...

output:

1 4

result:

ok 

Test #17:

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

input:

100 100
aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec
aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha
abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...

output:

1 4

result:

ok 

Test #18:

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

input:

100 100
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abababababababababababababababababababababababababababababababababababababababababababababababababab
acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...

output:

1 2

result:

ok 

Test #19:

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

input:

100 100
aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 100

result:

ok 

Test #20:

score: 0
Accepted
time: 22ms
memory: 47388kb

input:

500 10000
aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...

output:

1 11

result:

ok 

Test #21:

score: 0
Accepted
time: 25ms
memory: 47304kb

input:

500 10000
aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...

output:

1013 1022

result:

ok 

Test #22:

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

input:

3 5
cccca
ccgda
ccgia

output:

4 4

result:

ok 

Test #23:

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

input:

500 10000
aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...

output:

1317 1326

result:

ok 

Test #24:

score: 0
Accepted
time: 22ms
memory: 48556kb

input:

500 10000
aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...

output:

76 81

result:

ok 

Test #25:

score: 0
Accepted
time: 11ms
memory: 47328kb

input:

500 10000
acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...

output:

1 4

result:

ok 

Test #26:

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

input:

500 10000
aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...

output:

1 4

result:

ok 

Test #27:

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

input:

500 10000
abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...

output:

1 4

result:

ok 

Test #28:

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

input:

500 10000
abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...

output:

1 4

result:

ok 

Test #29:

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

input:

500 10000
acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...

output:

1 2

result:

ok 

Test #30:

score: 0
Accepted
time: 29ms
memory: 47436kb

input:

500 10000
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

9997 10000

result:

ok 

Test #31:

score: 0
Accepted
time: 16ms
memory: 47384kb

input:

500 10000
aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 4

result:

ok 

Test #32:

score: 0
Accepted
time: 16ms
memory: 47332kb

input:

500 10000
aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1 10000

result:

ok 

Test #33:

score: 0
Accepted
time: 19ms
memory: 48368kb

input:

500 10000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

6001 10000

result:

ok 

Test #34:

score: 0
Accepted
time: 19ms
memory: 47392kb

input:

500 10000
abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

8189 10000

result:

ok 

Test #35:

score: 0
Accepted
time: 40ms
memory: 54120kb

input:

500 20000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

18001 20000

result:

ok 

Test #36:

score: 0
Accepted
time: 41ms
memory: 54140kb

input:

500 20000
abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

16381 20000

result:

ok