| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6038 |
2014-06-15T19:54:46 Z |
ainta |
돌 옮기기 (GA7_stone) |
C++ |
|
0 ms |
5776 KB |
#pragma warning(disable:4996)
#include<stdio.h>
int X1[200100], X2[200100], n, L, c1, c2;
int p[200010], q[400010], oto[200010], be = -1, ed = -1;
long long Res, S;
void KMP(){
int i, pv = 0;
for (i = 0; i < c2*2-1; i++){
while (pv != -1 && p[pv] != q[i]){
pv = oto[pv];
}
pv++;
if (pv == c1){
if (be == -1)be = i - c1 + 1;
ed = i - c1 + 1;
pv = oto[pv];
}
}
}
long long Do(int be){
int i;
long long Sum = 0, t;
for (i = 0; i < n; i++){
t = X2[be] - X1[i];
if (t < 0) t += L;
Sum += t;
be++;
if (be == c2)be = 0;
}
return Sum;
}
int main(){
int i, x, t;
char pp[2];
scanf("%d%d", &L, &n);
Res = S = (long long)n*L;
for (i = 0; i < 2 * n; i++){
scanf("%d%s", &x, pp);
if (pp[0] == 'B'){
p[c1] = i;
X1[c1++] = x;
}
else{
q[c2] = i;
X2[c2++] = x;
}
}
p[c1] = p[0] + 2 * n;
q[c2] = q[0] + 2 * n;
for (i = 0; i < c1; i++)p[i] = p[i + 1] - p[i];
for (i = 0; i < c2; i++)q[i] = q[i + 1] - q[i];
for (i = c2; i < c2 * 2 - 1; i++)q[i] = q[i - c2];
oto[0] = -1;
for (i = 1; i <= c1; i++){
t = oto[i - 1];
while (t != -1 && p[t] != p[i - 1]){
t = oto[t];
}
oto[i] = t + 1;
}
KMP();
if (be == -1){
printf("-1\n");
return 0;
}
printf("%lld\n", Do(be) + S - Do(ed));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5776 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5776 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
5776 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
