제출 #6008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6008		model_code	돌 옮기기 (GA7_stone)	C++98	100 / 100	108 ms	15748 KiB

stone

#include<stdio.h>
#define min2(a,b) ((a)<(b)?(a):(b))

typedef long long lld;

int n, fail[1001001];
char col[1001001], riv[2002002];
lld ba[1001001], r, gap, dap=-1;

int main(){
	int i, j=1;
	scanf("%lld%d", &r, &n), n*=2;
	for(i=1; i<=n; i++){
		scanf("%lld %c", &ba[i], &col[i]);
		riv[i]=riv[n+i]=col[i];
	}
	col[n+1]='$';
	for(i=2; i<=n; i++){
		while(col[i]!=col[j]){
			if(j==1){
				j=0;
				break;
			}
			j=fail[j-1]+1;
		}
		fail[i]=j++;
	}
	for(i=j=1; i<=2*n; i++){
		while(riv[i]==col[j] || j==n+1){
			if(j==1){
				j=0;
				break;
			}
			j=fail[j-1]+1;
		}
		if(j==n){
			gap=r*min2(i-n, 2*n-i);
			if(dap==-1)dap=gap;
			else dap=min2(dap,gap);
		}
		j++;
	}
	printf("%lld", dap);
	return 0;
}

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