oj.uz

Submission #6040

# Submission time Handle Problem Language Result Execution time Memory
6040 2014-06-15T20:12:13 Z kriii 돌 옮기기 (GA7_stone) C++
56 / 100
 36 ms 9680 KB 
#include <stdio.h>

int R,N,X[600006]; long long S[600006];
char C[600006],P[200006]; int pi[200006];

long long abs(long long a){return a < 0 ? -a : a;}

int main()
{
	scanf ("%d %d",&R,&N); N *= 2;
	for (int i=N;i<2*N;i++){
		scanf ("%d %c",&X[i],&P[i-N]);
		X[i-N] = X[i] - R;
		X[i+N] = X[i] + R;
		C[i-N] = C[i+N] = C[i] = P[i-N];
		P[i-N] = (P[i-N] == 'B') ? 'W' : 'B';
	}

	S[0] = X[0];
	for (int i=1;i<3*N;i++) S[i] = S[i-1] + X[i];

	pi[0] = -1;
	for (int i=1,k=-1;i<N;i++){
		while (k >= 0 && P[k+1] != P[i]) k = pi[k];
		if (P[k+1] == P[i]) k++;
		pi[i] = k;
	}

	long long ans = 1ll << 62;
	for (int i=0,k=-1;i<6*N;i++){
		while (k >= 0 && P[k+1] != C[i]) k = pi[k];
		if (P[k+1] == C[i]){
			k++;
			if (k == N-1){
				long long a = S[2*N-1] - S[N-1];
				long long b = S[i] - S[i-N];
				long long c = abs(a - b);
				if (ans > c) ans = c;
				k = pi[k];
			}
			else continue;
		}
	}

	if (ans == 1ll << 62) ans = -1;
	printf ("%lld\n",ans);

	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9680 KB Output is correct
2 Correct 0 ms 9680 KB Output is correct
3 Correct 0 ms 9680 KB Output is correct
4 Correct 0 ms 9680 KB Output is correct
5 Correct 0 ms 9680 KB Output is correct
6 Correct 0 ms 9680 KB Output is correct
7 Correct 0 ms 9680 KB Output is correct
8 Correct 0 ms 9680 KB Output is correct
9 Correct 0 ms 9680 KB Output is correct
10 Correct 0 ms 9680 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9680 KB Output is correct
2 Correct 0 ms 9680 KB Output is correct
3 Correct 0 ms 9680 KB Output is correct
4 Correct 0 ms 9680 KB Output is correct
5 Correct 0 ms 9680 KB Output is correct
6 Correct 0 ms 9680 KB Output is correct
7 Correct 0 ms 9680 KB Output is correct
8 Correct 0 ms 9680 KB Output is correct
9 Correct 0 ms 9680 KB Output is correct
10 Correct 0 ms 9680 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9680 KB Output is correct
2 Correct 0 ms 9680 KB Output is correct
3 Correct 0 ms 9680 KB Output is correct
4 Correct 0 ms 9680 KB Output is correct
5 Correct 0 ms 9680 KB Output is correct
6 Correct 0 ms 9680 KB Output is correct
7 Correct 0 ms 9680 KB Output is correct
8 Correct 0 ms 9680 KB Output is correct
9 Correct 0 ms 9680 KB Output is correct
10 Correct 0 ms 9680 KB Output is correct
11 Correct 0 ms 9680 KB Output is correct
12 Correct 0 ms 9680 KB Output is correct
13 Correct 0 ms 9680 KB Output is correct
14 Correct 0 ms 9680 KB Output is correct
15 Correct 0 ms 9680 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9680 KB Output is correct
2 Correct 0 ms 9680 KB Output is correct
3 Correct 0 ms 9680 KB Output is correct
4 Correct 0 ms 9680 KB Output is correct
5 Correct 0 ms 9680 KB Output is correct
6 Correct 0 ms 9680 KB Output is correct
7 Correct 0 ms 9680 KB Output is correct
8 Correct 0 ms 9680 KB Output is correct
9 Correct 0 ms 9680 KB Output is correct
10 Correct 0 ms 9680 KB Output is correct
11 Correct 0 ms 9680 KB Output is correct
12 Correct 0 ms 9680 KB Output is correct
13 Correct 0 ms 9680 KB Output is correct
14 Correct 0 ms 9680 KB Output is correct
15 Correct 0 ms 9680 KB Output is correct
16 Correct 0 ms 9680 KB Output is correct
17 Correct 0 ms 9680 KB Output is correct
18 Correct 0 ms 9680 KB Output is correct
19 Correct 0 ms 9680 KB Output is correct
20 Correct 0 ms 9680 KB Output is correct

Subtask #5
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9680 KB Output is correct
2 Runtime error 20 ms 9676 KB SIGSEGV Segmentation fault
3 Halted 0 ms 0 KB -