QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395109 | #2704. Lexicographical Lecturing | kevinyang# | AC ✓ | 86ms | 54348kb | C++17 | 2.8kb | 2024-04-21 04:31:22 | 2024-04-21 04:31:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3,unroll-loops")
struct PolyHash{
/*
WARNING: make sure the values in the array or string are in the range [0,5e8]
*/
vector<ll>powers;
vector<ll>hashes;
ll seed = 500002961;
const ll mod = (ll)1e9+7;
vector<int>arr;
void init(int n){
powers.resize(n+5); powers[0] = 1;
hashes.resize(n+5);
for(int i = 1; i<=n; i++){
powers[i] = powers[i-1]*seed; powers[i]%=mod;
}
for(int i = 1; i<=n; i++){
hashes[i] = hashes[i-1]*seed+arr[i]; hashes[i]%=mod;
}
}
void init(int n, string s){//string is 0 indexed
arr.resize(n+5);
for(int i = 1; i<=n; i++){
arr[i] = s[i-1];
}
init(n);
}
void init(int n, vector<int>a){//a is 1 indexed
arr.resize(n+5);
for(int i = 1; i<=n; i++){
arr[i] = a[i];
}
init(n);
}
inline ll subhash(int l, int r){//inclusive
ll hsh = hashes[r]-hashes[l-1]*powers[r-l+1]%mod; hsh+=mod; hsh%=mod;
return hsh;
}
};
vector<PolyHash>hsh(505);
inline bool eq(int i, int j, int l, int r) {
return hsh[i].subhash(l,r) == hsh[j].subhash(l,r);
}
vector<string>arr(505);
inline bool smaller(int i, int j, int l, int r) {
int low = l-1;
int high = r+1;
while(low + 1 < high){
int mid = (low+high)/2;
if(eq(i,j,l,mid)){
low = mid;
}
else{
high = mid;
}
}
if(high == r+1)return false;
return arr[i][high-1] < arr[j][high-1];
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,m;
cin >> n >> m;
for(int i = 1; i<=n; i++){
cin >> arr[i];
}
vector<vector<int>>dp(n+1,vector<int>(m+2));
for(int j = m; j>=1; j--){
for(int i = 2; i<=n; i++){
if(arr[i][j-1] != arr[i-1][j-1]){
continue;
}
else{
dp[i][j] = dp[i][j+1]+1;
}
}
}
pair<int,int>p = {1,m};
int mn = m-1;
for(int j = 1; j<=m; j++){
bool good = true;
int mx = 0;
for(int i = 2; i<=n; i++){
int lcp = dp[i][j];
if(j+lcp == m+1){
good = false;
break;
}
if(arr[i-1][j-1+lcp] > arr[i][j-1+lcp]){
good = false;
break;
}
mx = max(mx,lcp);
}
if(!good)continue;
// cout << mx << '\n';
if(mx < mn){
mn = mx;
p = {j,j+mx};
}
//cout << j << ' ' << high << '\n';
}
cout << p.first << ' ' << p.second << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
2 1 a b
output:
1 1
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3740kb
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: 3872kb
input:
4 2 aa ab ba bb
output:
1 2
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3644kb
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: 3964kb
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: 3720kb
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: 3724kb
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: 3640kb
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: 3876kb
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: 3680kb
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: 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: 3944kb
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: 3940kb
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: 3592kb
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: 3796kb
input:
100 100 aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...
output:
1 4
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
100 100 aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...
output:
1 4
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
100 100 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa abababababababababababababababababababababababababababababababababababababababababababababababababab acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...
output:
1 2
result:
ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
100 100 aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 100
result:
ok
Test #20:
score: 0
Accepted
time: 39ms
memory: 28892kb
input:
500 10000 aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...
output:
1 11
result:
ok
Test #21:
score: 0
Accepted
time: 31ms
memory: 28736kb
input:
500 10000 aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...
output:
1013 1022
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 5 cccca ccgda ccgia
output:
4 4
result:
ok
Test #23:
score: 0
Accepted
time: 35ms
memory: 28664kb
input:
500 10000 aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...
output:
1317 1326
result:
ok
Test #24:
score: 0
Accepted
time: 42ms
memory: 28828kb
input:
500 10000 aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...
output:
76 81
result:
ok
Test #25:
score: 0
Accepted
time: 21ms
memory: 28764kb
input:
500 10000 acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...
output:
1 4
result:
ok
Test #26:
score: 0
Accepted
time: 16ms
memory: 28640kb
input:
500 10000 aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...
output:
1 4
result:
ok
Test #27:
score: 0
Accepted
time: 19ms
memory: 28704kb
input:
500 10000 abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...
output:
1 4
result:
ok
Test #28:
score: 0
Accepted
time: 32ms
memory: 28764kb
input:
500 10000 abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...
output:
1 4
result:
ok
Test #29:
score: 0
Accepted
time: 31ms
memory: 28672kb
input:
500 10000 acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...
output:
1 2
result:
ok
Test #30:
score: 0
Accepted
time: 45ms
memory: 28704kb
input:
500 10000 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
9997 10000
result:
ok
Test #31:
score: 0
Accepted
time: 21ms
memory: 28660kb
input:
500 10000 aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 4
result:
ok
Test #32:
score: 0
Accepted
time: 26ms
memory: 28828kb
input:
500 10000 aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 10000
result:
ok
Test #33:
score: 0
Accepted
time: 34ms
memory: 28744kb
input:
500 10000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
6001 10000
result:
ok
Test #34:
score: 0
Accepted
time: 46ms
memory: 28656kb
input:
500 10000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
8189 10000
result:
ok
Test #35:
score: 0
Accepted
time: 81ms
memory: 54348kb
input:
500 20000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18001 20000
result:
ok
Test #36:
score: 0
Accepted
time: 86ms
memory: 54316kb
input:
500 20000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16381 20000
result:
ok