QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717093#9522. A Simple String ProblemdefinierenAC ✓389ms156420kbC++146.9kb2024-11-06 16:51:182024-11-10 22:38:32

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 22:38:32]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:389ms
  • 内存:156420kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:50:07]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:389ms
  • 内存:158168kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-06 16:51:22]
  • 评测
  • 测评结果:100
  • 用时:351ms
  • 内存:102772kb
  • [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