Submission #6041

#	Time	Username	Problem	Language	Result	Execution time	Memory
6041		kriii	돌 옮기기 (GA7_stone)	C++98	100 / 100	100 ms	18276 KiB

stone

#include <stdio.h>

int R,N,X[1200006]; long long S[1200006];
char C[1200006],P[400006]; int pi[400006];

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 / 6
• Subtask 2: 11 / 11
• Subtask 3: 16 / 16
• Subtask 4: 23 / 23
• Subtask 5: 44 / 44