Submission #6768

#	Time	Username	Problem	Language	Result	Execution time	Memory
6768		cki86201	돌 옮기기 (GA7_stone)	C++98	100 / 100	96 ms	5776 KiB

stone

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;

int c[800040];
int f[400020];

int main()
{
	int r, n;
	int i;
	scanf("%d%d",&r,&n);
	for(i=1;i<=2*n;i++){
		char ch[2];
		scanf("%*d%s",ch);
		c[i] = ch[0] == 'B';
	}
	n = 2*n;
	for(i=1;i<=n;i++)c[i+n] = c[i];
	int m = 2*n;
	f[0] = -1;
	for(i=1;i<=n;i++){
		int x;
		for(x = f[i-1]+1;x;x = f[x-1]+1){
			if(c[i] == c[x])break;
		}
		f[i] = x;
	}
	int j = 1;
	for(i=1;i<=m;i++,j++){
		while(j && c[i] == c[j])j = f[j-1] + 1;
		if(j == n)break;
	}
	if(i-n == n+1)printf("-1");
	else printf("%lld",(ll)r*(i-n));
	return 0;
}

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