Submission #6605

#	Time	Username	Problem	Language	Result	Execution time	Memory
6605		Qwaz	돌 옮기기 (GA7_stone)	C++98	100 / 100	100 ms	3432 KiB

stone

#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX = 400020;

int circle, n;
bool data[MAX<<1];

void input(){
	scanf("%d%d", &circle, &n);
	n <<= 1;

	int i;
	for(i = 0; i<n; i++){
		char t[2];
		scanf("%*d%s", t);
		data[i+n] = data[i] = t[0] == 'W';
	}
}

int fail[MAX];

void calcFail(){
	fail[0] = -1;

	int i;
	for(i = 1; i<n; i++){
		int last = i-1;

		fail[i] = -1;
		while(last >= 0){
			if(data[i] == data[fail[last]+1]) {
				fail[i] = fail[last]+1;
				break;
			} else last = fail[last];
		}
	}
}

int res = 0;

void check(int pos){
	int t = min(pos, n-pos);
	if(res == 0 || res > t) res = t;
}

void match(){
	int f = 0, s;
	for(s = 0; s<2*n; s++){
		while(f > 0 && data[f] == data[s])
			f = fail[f-1]+1;
		if(data[f] != data[s]) f++;
		if(f == n){
			check(s-(n-1));
			f = fail[n-1]+1;
		}
	}
}

int main(){
	input();

	calcFail();
	match();

	printf("%lld\n", res == 0 ? -1 : (long long)res * circle);
	
	return 0;
}

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