QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717093 | #9522. A Simple String Problem | definieren | AC ✓ | 389ms | 156420kb | C++14 | 6.9kb | 2024-11-06 16:51:18 | 2024-11-10 22:38:32 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-11-06 16:51:18]
- 提交
answer
#include <bits/stdc++.h>
#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n'
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n'
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define dbg(x) void()
#define dpi(x, y) void()
#define dbgf(fmt, args...) void()
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ldb = long double;
using i128 = __int128_t;
using ui128 = __uint128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;
bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T Norm(T a, T p = MOD) { return (a % p + p) % p; }
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }
template<typename T> T DivFloor(T a, T b) { return a >= 0 ? a / b : (a - b + 1) / b; }
template<typename T> T DivCeil(T a, T b) { return a >= 0 ? (a + b - 1) / b : a / b; }
namespace FastIO {
constexpr int LEN = 1 << 20;
char in[LEN + 1], out[LEN + 1];
char *pin = in, *pout = out, *ein = in, *eout = out + LEN;
char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
struct Flush { ~Flush() { fwrite(out, 1, pout - out, stdout); pout = out; return; } } _flush;
template<typename T> T Read() {
T x = 0; int f = 1; char ch = gc();
while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return x * f;
}
void Read(char *s) {
char ch = gc();
while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = gc();
while ((ch != EOF) && !(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')) *s = ch, s ++, ch = gc();
*s = '\0'; return;
}
template<typename T> void Read(T &x) { x = Read<T>(); return; }
template<typename T, typename ...Args>
void Read(T &x, Args &...args) { Read(x), Read(args...); return; }
template<typename T> void Write(T x) {
static char stk[40]; int tp = 0;
if (x < 0) pc('-'), x = ~x + 1;
do stk[tp++] = x % 10 + 48, x /= 10; while (x);
while (tp --) pc(stk[tp]);
return;
}
void Write(char ch) { pc(ch); return; }
void Write(const char *s) {
while (*s != '\0') pc(*s), s ++;
return;
}
void Puts(const char *s) {
Write(s), pc('\n'); return;
}
template<typename T, typename ...Args>
void Write(T x, Args ...args) { Write(x), Write(args...); return; }
}
using FastIO::Read;
using FastIO::Write;
using FastIO::Puts;
#define getchar FastIO::gc
#define putchar FastIO::pc
constexpr int N = 8e5 + 5;
int n, L[2][N], R[2][N];
char s[2][N], t[N << 2];
struct Suffix_Array {
static constexpr int N = ::N << 2, LG = 20;
int n, rk[N], sa[N], ork[N], id[N], pid[N], bin[N], st[LG][N];
char s[N];
void Build(char _s[]) {
n = strlen(_s + 1); int m = 256, p = 0;
auto cmp = [&](int i, int j, int w) -> bool
{ return ork[i] == ork[j] && ork[i + w] == ork[j + w]; };
for (int i = 1; i <= n; i ++) s[i] = _s[i];
for (int i = 1; i <= n; i ++) bin[rk[i] = s[i]] ++;
for (int i = 1; i <= m; i ++) bin[i] += bin[i - 1];
for (int i = n; i >= 1; i --) sa[bin[rk[i]] --] = i;
for (int w = 1; ; w <<= 1, m = p, p = 0) {
for (int i = n; i > n - w; i --) id[++ p] = i;
for (int i = 1; i <= n; i ++) if (sa[i] > w) id[++ p] = sa[i] - w;
for (int i = 1; i <= m; i ++) bin[i] = 0;
for (int i = 1; i <= n; i ++) bin[pid[i] = rk[id[i]]] ++;
for (int i = 1; i <= m; i ++) bin[i] += bin[i - 1];
for (int i = n; i >= 1; i --) sa[bin[pid[i]] --] = id[i];
for (int i = 1; i <= n; i ++) ork[i] = rk[i]; p = 0;
for (int i = 1; i <= n; i ++) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++ p;
if (p == n) break;
}
for (int i = 1, j = 0; i <= n; i ++) {
if (j) j --;
while (s[i + j] == s[sa[rk[i] - 1] + j]) j ++;
st[0][rk[i]] = j;
}
for (int i = 1; i <= __lg(n); i ++)
for (int j = 1; j + (1 << i) - 1 <= n; j ++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
return;
}
int Query(int l, int r) {
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
int Get_Lcp(int i, int j) {
if (!i || !j) return 0;
if ((i = rk[i]) > (j = rk[j])) swap(i, j);
if (i == j) return n; return Query(i + 1, j);
}
} sa;
void slv() {
n = Read<int>() + 1;
Read(s[0] + 1), s[0][n] = '!';
s[1][1] = '@', Read(s[1] + 2);
{
int m = 0;
for (int i = 1; i <= n; i ++) t[L[0][i] = ++ m] = s[0][i]; t[++ m] = '#';
for (int i = 1; i <= n; i ++) t[L[1][i] = ++ m] = s[1][i]; t[++ m] = '$';
for (int i = 1; i <= n; i ++) t[R[0][n - i + 1] = ++ m] = s[0][n - i + 1]; t[++ m] = '%';
for (int i = 1; i <= n; i ++) t[R[1][n - i + 1] = ++ m] = s[1][n - i + 1]; t[++ m] = '^';
sa.Build(t);
};
for (int len = n >> 1; len; len --) {
for (int l = 1, r = len; l <= n; l += len, r += len) {
int x = sa.Get_Lcp(L[1][l], L[1][r + 1]), y = sa.Get_Lcp(R[1][l - 1], R[1][r]);
if (l - 1 - y > 0) y += sa.Get_Lcp(R[0][l - 1 - y], R[1][r - y]);
if (x + y >= len) { Write(len << 1, '\n'); return; }
x = sa.Get_Lcp(R[0][l - 1], R[0][r]), y = sa.Get_Lcp(L[0][l], L[0][r + 1]);
if (r + 1 + y <= n) y += sa.Get_Lcp(L[0][l + y], L[1][r + 1 + y]);
if (x + y >= len) { Write(len << 1, '\n'); return; }
x = sa.Get_Lcp(R[0][l - 1], R[1][r]), y = sa.Get_Lcp(L[0][l], L[1][r + 1]);
if (r + 1 + y <= n) y += sa.Get_Lcp(L[1][l + y], L[1][r + 1 + y]);
if (x + y >= len) { Write(len << 1, '\n'); return; }
x = sa.Get_Lcp(R[0][l - 1], R[1][r]), y = sa.Get_Lcp(L[0][l], L[1][r + 1]);
if (l - 1 - x > 0) x += sa.Get_Lcp(R[0][l - 1 - x], R[0][r - x]);
if (x + y >= len) { Write(len << 1, '\n'); return; }
}
}
Puts("0");
return;
}
void clr() {
return;
}
bool Med;
int main() {
#ifdef LOCAL
freopen("!in.in", "r", stdin);
freopen("!out.out", "w", stdout);
fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
int T = 1;
// int T = Read<int>();
while (T --) slv(), clr();
#ifdef LOCAL
fprintf(stderr, "%d ms\n", (int)clock());
#endif
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38432kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 42552kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 40568kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 3ms
memory: 42552kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 42552kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 40500kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 270ms
memory: 156420kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 238ms
memory: 153756kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 276ms
memory: 153028kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 389ms
memory: 148776kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 188ms
memory: 147428kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 202ms
memory: 155816kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 287ms
memory: 149412kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 42496kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 42544kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 44660kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 44592kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 40500kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 3ms
memory: 36432kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 48756kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 44672kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed