oj.uz

답안 #6038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6038 2014-06-15T19:54:46 Z ainta 돌 옮기기 (GA7_stone) C++
0 / 100
 0 ms 5776 KB 
#pragma warning(disable:4996)
#include<stdio.h>
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;
		}
	}
	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
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5776 KB Output is correct
2 Correct 0 ms 5776 KB Output is correct
3 Incorrect 0 ms 5776 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -