QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188945 | #2704. Lexicographical Lecturing | triplem5ds# | AC ✓ | 46ms | 14876kb | C++23 | 1.4kb | 2023-09-26 17:39:04 | 2023-09-26 17:39:04 |
Judging History
answer
/// Msaa el 5ra
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for(int i = a; i < b; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll
using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;
const int N = 5e5 + 5, LG = 18, MOD = 1e9 + 7;
const long double PI = acos(-1);
const long double EPS = 1e-7;
void doWork() {
int n, l;
cin >> n >> l;
vector<string> vs(n);
f(i, 0, n) cin >> vs[i];
vector<int> val(n, INT_MAX);
array<int, 3> ans({l, 1, l});
for (int i = l - 1; i >= 0; --i) {
int r = 0;
f(j, 1, n) {
if (vs[j][i] > vs[j - 1][i])val[j] = i;
if (vs[j][i] < vs[j - 1][i])val[j] = INT_MAX;
r = max(r, val[j]);
}
if ((r - i + 1) <= ans[0]) {
ans = {r - i + 1, i + 1, r + 1};
}
}
cout << ans[1] << ' ' << ans[2] << '\n';
}
int32_t main() {
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif // ONLINE_JUDGE
int t = 1;
// cin >> t;
while (t--) {
doWork();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3500kb
input:
2 1 a b
output:
1 1
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3464kb
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: 3508kb
input:
4 2 aa ab ba bb
output:
1 2
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3488kb
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: 3504kb
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: 3552kb
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: 3464kb
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: 3472kb
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: 3472kb
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: 3432kb
input:
4 6 aaaaaa aaabbb aaacaa aaacac
output:
4 6
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3444kb
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: 3548kb
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: 3436kb
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: 3424kb
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: 3456kb
input:
100 100 aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...
output:
1 4
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
100 100 aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...
output:
1 4
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
100 100 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa abababababababababababababababababababababababababababababababababababababababababababababababababab acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...
output:
1 2
result:
ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
100 100 aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 100
result:
ok
Test #20:
score: 0
Accepted
time: 40ms
memory: 9084kb
input:
500 10000 aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...
output:
1 11
result:
ok
Test #21:
score: 0
Accepted
time: 46ms
memory: 9164kb
input:
500 10000 aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...
output:
1013 1022
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3376kb
input:
3 5 cccca ccgda ccgia
output:
4 4
result:
ok
Test #23:
score: 0
Accepted
time: 35ms
memory: 9148kb
input:
500 10000 aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...
output:
1317 1326
result:
ok
Test #24:
score: 0
Accepted
time: 28ms
memory: 9160kb
input:
500 10000 aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...
output:
76 81
result:
ok
Test #25:
score: 0
Accepted
time: 27ms
memory: 9088kb
input:
500 10000 acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...
output:
1 4
result:
ok
Test #26:
score: 0
Accepted
time: 31ms
memory: 9136kb
input:
500 10000 aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...
output:
1 4
result:
ok
Test #27:
score: 0
Accepted
time: 30ms
memory: 9132kb
input:
500 10000 abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...
output:
1 4
result:
ok
Test #28:
score: 0
Accepted
time: 34ms
memory: 9132kb
input:
500 10000 abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...
output:
1 4
result:
ok
Test #29:
score: 0
Accepted
time: 13ms
memory: 9120kb
input:
500 10000 acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...
output:
1 2
result:
ok
Test #30:
score: 0
Accepted
time: 16ms
memory: 9128kb
input:
500 10000 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
9997 10000
result:
ok
Test #31:
score: 0
Accepted
time: 13ms
memory: 9156kb
input:
500 10000 aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 4
result:
ok
Test #32:
score: 0
Accepted
time: 12ms
memory: 9064kb
input:
500 10000 aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 10000
result:
ok
Test #33:
score: 0
Accepted
time: 5ms
memory: 9208kb
input:
500 10000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
6001 10000
result:
ok
Test #34:
score: 0
Accepted
time: 4ms
memory: 9176kb
input:
500 10000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
8189 10000
result:
ok
Test #35:
score: 0
Accepted
time: 26ms
memory: 14876kb
input:
500 20000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18001 20000
result:
ok
Test #36:
score: 0
Accepted
time: 20ms
memory: 14868kb
input:
500 20000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16381 20000
result:
ok