oj.uz

Submission #6604

# Submission time Handle Problem Language Result Execution time Memory
6604 2014-07-01T14:21:08 Z Qwaz 돌 옮기기 (GA7_stone) C++
0 / 100
 0 ms 3432 KB 
#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 * n);
	
	return 0;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3432 KB Output is correct
2 Correct 0 ms 3432 KB Output is correct
3 Incorrect 0 ms 3432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -