Submission #477395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477395	2021-10-02T02:09:57 Z	ace_in_the_hole	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	373 ms	464 KB

necklace

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 100;
int pi[MAX], pi_rev[MAX];

void calc(string& s, int (&pi)[MAX]) {
	pi[0] = 0;
	int n = s.size();
	for (int j = 0, i = 1; i < n; i++) {
		pi[i] = 0;
		while (s[j] != s[i]) {
			if (j == 0) break;
			j = pi[j-1];
		}
		if (s[i] == s[j]) pi[i] = ++j;
	}	
}
int suff[MAX], pref[MAX];
void maximize(int& var, const int& val) { if (val > var) var = val;}

int m,n, longest = 0, idx_a, idx_b;
#define cst const string&
void find_necklace(cst a, cst b, cst a_rev, cst b_rev, const int& shift, bool rev) {
	for (int i = 0; i <= n; i++) suff[i] = pref[i] = 0;
	string word = a + '$' + b;
	calc(word, pi);
	for (int i = m+1; i <= m+n; i++) suff[i-m] = pi[i];
	word = a_rev + '$' + b_rev;
	calc(word, pi_rev);
	for (int i = m+1; i <= m+n; i++) 
		if (pi_rev[i]) maximize(pref[n-(i-m)+pi_rev[i]], pi_rev[i]);
//	if (shift == 5) cerr << "HELLO. " << a << " vs. " << b << "\n";
//	for (int i = 1; i <= n; i++) cerr << pref[i] << ' '; cerr << '\n';
//	for (int i = 1; i <= n; i++) cerr << suff[i] << ' '; cerr << '\n';
	for (int i = 1; i <= n; i++) {
		int length = pref[i] + suff[i-pref[i]];
		if (length > longest) {
			int ib = rev ? n-i : i-length;
			int ia = (suff[i-pref[i]]-length+shift+m) % m;
			if (length >= m) ia = 0; 
			if (ia + length <= m)
//				cerr << "comparing " << a << " with " << b << '\n',
//				cerr << "start at b[" << i << "] --> ",
//				cerr << length << '/' << suff[i-pref[i]] << ',' << i << '\n',
				longest = length, idx_b = ib, idx_a = ia;
		}
	}
	/* 
	abcd
	cdab
	
	abcd
	badc
	
	azbc
	bxac
	
	abc
	bac
	*/
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
//	freopen("debug.txt", "w", stderr);
	string A, B;
	cin >> A >> B;
	string B_rev = B, A_rev = A;
	reverse(B_rev.begin(), B_rev.end());
	reverse(A_rev.begin(), A_rev.end());
	::m = (int) A.size();
	::n = (int) B.size();
	for (int shift = 0; shift < m; shift++) {
		find_necklace(A, B, A_rev, B_rev, shift, false);	
		find_necklace(A, B_rev, A_rev, B, shift, true);	
		
		A.push_back(A.front());
		A.erase(0,1);
		A_rev = A;
		reverse(A_rev.begin(), A_rev.end());
	}
	printf("%d\n%d %d", longest, idx_a, idx_b);
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	327 ms	440 KB	Output is correct
2	Correct	252 ms	336 KB	Output is correct
3	Correct	373 ms	416 KB	Output is correct
4	Correct	246 ms	408 KB	Output is correct
5	Correct	158 ms	432 KB	Output is correct
6	Correct	169 ms	456 KB	Output is correct
7	Correct	223 ms	464 KB	Output is correct
8	Correct	269 ms	464 KB	Output is correct
9	Correct	285 ms	336 KB	Output is correct