QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191621 | #2704. Lexicographical Lecturing | beshoyhany# | AC ✓ | 873ms | 54420kb | C++17 | 3.5kb | 2023-09-30 03:17:46 | 2023-09-30 03:17:46 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast,no-stack-protector", "omit-frame-pointer", "inline", "-ffast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,fma,popcnt,abm,mmx,avx")
#include<bits/stdc++.h>
#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll
using namespace std;
void Drakon() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Clion
freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 2e4 + 5, LOG = 25;
ll gcd(ll x, ll y) {
return y ? gcd(y, x % y) : x;
}
ll lcm(ll a, ll b) {
return (a * b) / __gcd(a, b);
}
int mul(int a, int b) {
ll ret = 1ll * a * b;
if(ret >= MOD)ret %= MOD;
return ret;
}
int add(int a, int b) {
if(a < 0)a += MOD;
if(b < 0)b += MOD;
a += b;
if(a >= MOD)a -= MOD;
return a;
}
int pw(int x, int y) {
int ret = 1;
while (y > 0) {
if (y % 2 == 0) {
x = mul(x, x);
y = y / 2;
} else {
ret = mul(ret, x);
y = y - 1;
}
}
return ret;
}
const int P1 = 31, P2 = 37;
int pw1[N], pw2[N], inv1[N], inv2[N];
void pre() {
pw1[0] = inv1[0] = pw2[0] = inv2[0] = 1;
int mulInv1 = pw(P1, MOD - 2);
int mulInv2 = pw(P2, MOD - 2);
for (int i = 1; i < N; i++) {
pw1[i] = mul(pw1[i - 1], P1);
pw2[i] = mul(pw2[i - 1], P2);
inv1[i] = mul(inv1[i - 1], mulInv1);
inv2[i] = mul(inv2[i - 1], mulInv2);
}
}
struct Hash {
vector<int> prefixHash;
Hash() {
}
Hash(string &s) {
prefixHash = vector<int>(s.size(), 0);
for (int i = 0; i < s.size(); i++) {
prefixHash[i] = mul(s[i] - 'a' + 1, pw1[i]);
if (i)
prefixHash[i] = add(prefixHash[i], prefixHash[i - 1]);
}
}
int getRangeHashVal(int l, int r) {
return mul(add(prefixHash[r], -(l ? prefixHash[l - 1] : 0)), inv1[l]);
}
};
void solve() {
int n, l;
cin >> n >> l;
vector<Hash> vec(n);
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
sort(all(s));
for (int i = 0; i < n; ++i) {
vec[i] = Hash(s[i]);
}
int a = 0, b = l - 1;
for (int i = 0; i < l; ++i) {
int mx = i;
for (int j = 1; j < n; ++j) {
int st = i, en = l - 1, ind = -1;
while (st <= en){
int mid = (st + en) / 2;
if(vec[j].getRangeHashVal(i, mid) != vec[j - 1].getRangeHashVal(i, mid)){
ind = mid;
en = mid - 1;
}
else{
st = mid + 1;
}
}
if(!~ind || s[j][ind] < s[j - 1][ind]){
mx = 1e9;
break;
}
mx = max(mx, ind);
}
if((mx - i + 1) < (b - a + 1)){
a = i, b = mx;
}
}
cout << a + 1 << ' ' << b + 1;
}
signed main() {
Drakon();
pre();
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3936kb
input:
2 1 a b
output:
1 1
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
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: 3932kb
input:
4 2 aa ab ba bb
output:
1 2
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 4160kb
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: 4212kb
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: 3884kb
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: 3888kb
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: 1ms
memory: 3864kb
input:
10 10 azzzzzzzzz bzzzzzzzzz czzzzzzzzz dzzzzzzzzz ezzzzzzzzz zzzzzzzzza zzzzzzzzzb zzzzzzzzzc zzzzzzzzzd zzzzzzzzze
output:
1 10
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3928kb
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: 3992kb
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: 3884kb
input:
4 6 aaaaaa aaabbb aaacaa aaacac
output:
4 6
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
10 10 aacbaacaac abacabaabb acbaabcabc acbcacabac bcbbbaabbb caaababcba cbaabbacbb cbbbcbacbc cbcacbcccb cbcccccccc
output:
5 7
result:
ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 4168kb
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: 4124kb
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: 3960kb
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: 3984kb
input:
100 100 aaebigffgfbjihciehifhbgdcfjibdeibfeifbefgbbaabgaigdgebgaijiejgffiibdhbjjjeabcaiagddaijagafcfhcbhejid abbchdecgidffbibegcgdheghdajdgbdiifbacifgedddhfgdfadiidgeidecebfejigcajdihjiidbjeafbiciihgiiiggabfjd adchagaibaejhbjiebiggdabhbjcbahadacecebjddghgfdggdabejfacagcecahdjfjbjeagdgdgbgiababfiijee...
output:
1 4
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
100 100 aabbgeggiaagdcbajcdbaaffcbaajjceijaaajgcdibbjcabbaggijaaabjacidhaafigccfgeghfaahjajhiifgcabhcgdjfeec aadaeacciabcchddhijbaagegeabhhadjeabcaededaijgabhefeebeacecbajjhaagdjcgjfehdcabafbjjcbbibabheeiajiha abfeccgfcabgaaahabfhabaebdacciehcbabdbedcbaedgadegehejeadaijcadaabfbaedfbeeigabcgcjicjajga...
output:
1 4
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 4148kb
input:
100 100 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa abababababababababababababababababababababababababababababababababababababababababababababababababab acacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacacac...
output:
1 2
result:
ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 4232kb
input:
100 100 aaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz aadzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 100
result:
ok
Test #20:
score: 0
Accepted
time: 36ms
memory: 28972kb
input:
500 10000 aaaaacbaaaaacbcabbbbacbbbbcacabccaaabcbaaacabcaaabcbaabbcbabccbbabbacaababccbbccbacccccacacaabbbcaaccabaaccbabbabcaaaaaccbacbbcabcccacaaaaabbcbbcaaabaccabaababbcabcababccbaacabacbbcbaabbbcabbabbbabccccacabababcaabcbbcbabbabaabaaaacabccbacaccbbccbaacbbaaaaccaacaccacbacaacaabbaaabaccabaccbba...
output:
1 11
result:
ok
Test #21:
score: 0
Accepted
time: 32ms
memory: 28904kb
input:
500 10000 aaaaababcbaacbbcbbacbbcbbaaaccbaacacabaaccabccbaaacccababaabccaacababbcaabbaacacaaabbcccbcaaacabbbbcaccbbcccbbaacbacabbabccaccbcccacbabcacbacaaccabbcabcccbbcaabaccccbbaaabbcaacbcbbcbbcabcbbbbbabbbbacbbbbcccabcccbcacbaaacbcaaaacaccabaabccbbccccbcbacbcbbbaacbcbaabbccabcbccabbbbbcabaaaaabccac...
output:
1013 1022
result:
ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 4124kb
input:
3 5 cccca ccgda ccgia
output:
4 4
result:
ok
Test #23:
score: 0
Accepted
time: 32ms
memory: 29004kb
input:
500 10000 aaaaaacacbabbcbcacbabbbbcbbbabbaccbcbbcabcbcbccbaaaabcccbaaccaabacbaacbcaabcccbacbaccbaaaacbaaaacaaaaaccababaaaaaaacabbabaccacbcccccbacacbacbcacbcabbacacbbabaacbcacbbccbbaabbcbbaaaabacabcaabbccacbabaaaaaaaaabccaacbacaabbababbabbcbbacccbbbcaccacbcaabacbacbaabaaccaaaaaabccbaaabccabababacbabc...
output:
1317 1326
result:
ok
Test #24:
score: 0
Accepted
time: 109ms
memory: 28884kb
input:
500 10000 aaaaaaaaaaaaacaaaabacbabaaaaaccaccacaaaaaabaaaaaaaacbcabacaaaaaabaaaaabbaacaaaaabaaaaaababbcbcaaaabbbaacbcaaaaaaaacacbaaaaaaaaaaaabaaaaaaaabcbbaaaaababaaaaaaaacccaaaaaabbaaaaaaaccbacccabaaaaaaaaaaaaababcccaaaaaaaaaaaabcaaaaaaccbbaaaaababcaaaaacbaaaaaacaaaaaaaccbccbcaaaaaabbaaaaaccccbaaaaac...
output:
76 81
result:
ok
Test #25:
score: 0
Accepted
time: 23ms
memory: 28912kb
input:
500 10000 acvhalrcggooxaeemjpctxggiqhjbrjvvfpjsxwdvnffrfthypvotpdbotktsevjyxyrchlldztsjrilyzkzbudhdnwdhqsffyiyodddkeryhoeorinvewkcxrlgeddmumrikbppmxxqidhwwqphlctlktoxezogkbfvqycgjhrevosznozohjhfmgljmsqvkvbhaqgplzakfqncxiklhfsbubrohnwjwziiknlubzavbozbriayiuzmzmimpfreivgrxxresadlrnfiwpfebgeyuighnwpmtr...
output:
1 4
result:
ok
Test #26:
score: 0
Accepted
time: 18ms
memory: 28964kb
input:
500 10000 aaclkzvhnbftbqvhlkaetwreybexhosegimrplnbnoeobbrgqkceiqawrruknelanrwejsihiermhonpvwdpesbmkpwgjadvyzibjpfrqoysvubznixiyfpuychdagyfctlwuhrhngnypcvvvuurogkzlcoqrnpxdqfppgeksskjfytkauapveoxrxpawxtlwwoyacctenkcdtjypupfmznmckkqwfjptfxnwhgsmjgmllmfqateunuvwqgyngwjgaadffkmxztcazgzhblpmyqqjbdcpvsspp...
output:
1 4
result:
ok
Test #27:
score: 0
Accepted
time: 30ms
memory: 28904kb
input:
500 10000 abdhncrkdsbczzppobrbfnapctpmansxuzvwvokusuxborgtrzezqlmzgvwsbeqmazxgndkvrapfeanoxthlyublnwiqesejwwnqyghgaaxmbuwwuwkcbhwbfmhkfbhwyfusoynutawlwqpopyccxroeskvbaaiukutyacxlukuqwqjtpwxjuztcmlfakwrpuxaaqanzglqsjfvhgmaxiflmznklkvjvbasdpjrqubfffnvrnngdzaakftaadedgbvbhsfwjqbhermtxafdyogabgzwcpvkocq...
output:
1 4
result:
ok
Test #28:
score: 0
Accepted
time: 81ms
memory: 29072kb
input:
500 10000 abgivsaauvpxwclsaauvaxoaagrbjkuaaohjalkghsabwtouyyckxzgaaqvltnexkwiabhaqwytvuylnxzaaaafyvpaakcwtsmdhqfabfhsnuaahkxazsqamnmacotaawxdfyjaaglfoppaadfsxrabfnydnlzweopaaopvwvawjabaowrroqhyvcabwalytaawlsnscaagsstmaabziyjjayhactmfpryhsenjuvaaamcsqnepeaazqpphkhacvyqzgpsizaaarcfegsuaabgyubpdlaihkaf...
output:
1 4
result:
ok
Test #29:
score: 0
Accepted
time: 243ms
memory: 29112kb
input:
500 10000 acaaaaaaababaaaaabacaaaaaaaaaaababaaaaabaaaaaaaaacaaaaabaaaaaaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaababaaabaaaaaaaaaaaaaaaaaaabacaaaaaaabaaabaaaaaaaaababaaaaaaaaaaadacababaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaabaaababaaacacaaaeababab...
output:
1 2
result:
ok
Test #30:
score: 0
Accepted
time: 424ms
memory: 28988kb
input:
500 10000 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
9997 10000
result:
ok
Test #31:
score: 0
Accepted
time: 22ms
memory: 28900kb
input:
500 10000 aaabzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 4
result:
ok
Test #32:
score: 0
Accepted
time: 26ms
memory: 28968kb
input:
500 10000 aaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
1 10000
result:
ok
Test #33:
score: 0
Accepted
time: 283ms
memory: 28904kb
input:
500 10000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
6001 10000
result:
ok
Test #34:
score: 0
Accepted
time: 354ms
memory: 28948kb
input:
500 10000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
8189 10000
result:
ok
Test #35:
score: 0
Accepted
time: 873ms
memory: 54420kb
input:
500 20000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
18001 20000
result:
ok
Test #36:
score: 0
Accepted
time: 771ms
memory: 54292kb
input:
500 20000 abaaabaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16381 20000
result:
ok