QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61023#2704. Lexicographical Lecturingabdelrahman001AC ✓69ms54660kbC++201.5kb2022-11-09 06:17:202022-11-09 06:17:23

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-09 06:17:23]
  • Judged
  • Verdict: AC
  • Time: 69ms
  • Memory: 54660kb
  • [2022-11-09 06:17:20]
  • Submitted

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