| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6041 |
2014-06-15T20:13:16 Z |
kriii |
돌 옮기기 (GA7_stone) |
C++ |
|
100 ms |
18276 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
18276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
18276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
18276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 4 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 5 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 6 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 7 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 8 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 9 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 10 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 11 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 12 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 13 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 14 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 15 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 16 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 17 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 18 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 19 |
Correct |
0 ms |
18276 KB |
Output is correct |
| 20 |
Correct |
0 ms |
18276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
18276 KB |
Output is correct |
| 2 |
Correct |
52 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
36 ms |
18276 KB |
Output is correct |
| 4 |
Correct |
24 ms |
18276 KB |
Output is correct |
| 5 |
Correct |
48 ms |
18276 KB |
Output is correct |
| 6 |
Correct |
84 ms |
18276 KB |
Output is correct |
| 7 |
Correct |
72 ms |
18276 KB |
Output is correct |
| 8 |
Correct |
88 ms |
18276 KB |
Output is correct |
| 9 |
Correct |
72 ms |
18276 KB |
Output is correct |
| 10 |
Correct |
96 ms |
18276 KB |
Output is correct |
| 11 |
Correct |
68 ms |
18276 KB |
Output is correct |
| 12 |
Correct |
84 ms |
18276 KB |
Output is correct |
| 13 |
Correct |
88 ms |
18276 KB |
Output is correct |
| 14 |
Correct |
100 ms |
18276 KB |
Output is correct |
| 15 |
Correct |
92 ms |
18276 KB |
Output is correct |
| 16 |
Correct |
92 ms |
18276 KB |
Output is correct |
| 17 |
Correct |
96 ms |
18276 KB |
Output is correct |
| 18 |
Correct |
84 ms |
18276 KB |
Output is correct |
| 19 |
Correct |
84 ms |
18276 KB |
Output is correct |
| 20 |
Correct |
88 ms |
18276 KB |
Output is correct |
| 21 |
Correct |
80 ms |
18276 KB |
Output is correct |
| 22 |
Correct |
88 ms |
18276 KB |
Output is correct |
| 23 |
Correct |
100 ms |
18276 KB |
Output is correct |
| 24 |
Correct |
96 ms |
18276 KB |
Output is correct |
| 25 |
Correct |
80 ms |
18276 KB |
Output is correct |
| 26 |
Correct |
92 ms |
18276 KB |
Output is correct |
| 27 |
Correct |
80 ms |
18276 KB |
Output is correct |
| 28 |
Correct |
96 ms |
18276 KB |
Output is correct |
| 29 |
Correct |
84 ms |
18276 KB |
Output is correct |
| 30 |
Correct |
92 ms |
18276 KB |
Output is correct |
