Submission #6039

#	Time	Username	Problem	Language	Result	Execution time	Memory
6039		ainta	돌 옮기기 (GA7_stone)	C++98	100 / 100	100 ms	5776 KiB

stone

#include<stdio.h>
#include<algorithm>
using namespace std;
int X1[200100], X2[200100], n, L, c1, c2;
int p[200010], q[400010], oto[200010], be = -1, ed = -1;
long long Res, S;
void KMP(){
	int i, pv = 0;
	for (i = 0; i < c2*2-1; i++){
		while (pv != -1 && p[pv] != q[i]){
			pv = oto[pv];
		}
		pv++;
		if (pv == c1){
			if (be == -1)be = i - c1 + 1;
			ed = i - c1 + 1;
			pv = oto[pv];
		}
	}
}
long long Do(int be){
	int i;
	long long Sum = 0, t;
	for (i = 0; i < n; i++){
		t = X2[be] - X1[i];
		if (t < 0) t += L;
		Sum += t;
		be++;
		if (be == c2)be = 0;
	}
	return Sum;
}
int main(){
	int i, x, t;
	char pp[2];
	scanf("%d%d", &L, &n);
	Res = S = (long long)n*L;
	for (i = 0; i < 2 * n; i++){
		scanf("%d%s", &x, pp);
		if (pp[0] == 'B'){
			p[c1] = i;
			X1[c1++] = x;
		}
		else{
			q[c2] = i;
			X2[c2++] = x;
		}
	}
	if (p[0] > q[0]){
		for (i = 0; i < n; i++){
			swap(p[i], q[i]);
			swap(X1[i], X2[i]);
		}
	}
	p[c1] = p[0] + 2 * n;
	q[c2] = q[0] + 2 * n;
	for (i = 0; i < c1; i++)p[i] = p[i + 1] - p[i];
	for (i = 0; i < c2; i++)q[i] = q[i + 1] - q[i];
	for (i = c2; i < c2 * 2 - 1; i++)q[i] = q[i - c2];
	oto[0] = -1;
	for (i = 1; i <= c1; i++){
		t = oto[i - 1];
		while (t != -1 && p[t] != p[i - 1]){
			t = oto[t];
		}
		oto[i] = t + 1;
	}
	KMP();
	if (be == -1){
		printf("-1\n");
		return 0;
	}
	printf("%lld\n", Do(be) + S - Do(ed));
}

• Subtask 1: 6 / 6
• Subtask 2: 11 / 11
• Subtask 3: 16 / 16
• Subtask 4: 23 / 23
• Subtask 5: 44 / 44