# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
53969 | 2018-07-02T06:22:23 Z | khsoo01 | Linear Garden (IOI08_linear_garden) | C++11 | 32 ms | 5516 KB |
#include<bits/stdc++.h> using namespace std; const int N = 1000005; int n, m, dt[N/2] = {1}, two[N/2] = {1}; char a[N]; int main() { scanf("%d%d%s",&n,&m,a+1); for(int i=1;2*i<=n;i++) { two[i] = two[i-1] * 2 % m; } if(n%2) dt[0]++; for(int i=1;2*i<=n;i++) { dt[i] = (dt[i-1] + two[i-1] + two[i-1 + n%2]) % m; } int typ = 0, ans = 1; for(int i=1;2*i<=n;i++) { if(i == 1) { if(a[1] == 'P' && a[2] == 'P') { ans = (ans + two[(n-2*i)/2] + 2 * dt[n/2-i]) % m; } if(a[1] == 'P' && a[2] == 'L') { ans = (ans + two[(n-2*i)/2] + dt[n/2-i]) % m; } if(a[1] == 'L' && a[2] == 'P') { ans = (ans + two[(n-2*i)/2]) % m; } if(a[1] == a[2]) typ = 1; } else if(typ == 1) { if(a[2*i] == 'P') { ans = (ans + two[(n-2*i)/2]) % m; } } else if(typ == 2) { if(a[2*i] == 'L') { ans = (ans + two[(n-2*i+1)/2]) % m; } } else if(a[2*i-1] == a[1] && a[2*i] == a[2]) { if(a[1] == 'P') { ans = (ans + two[(n-2*i+1)/2]) % m; } else { ans = (ans + two[(n-2*i)/2]) % m; } } else { if(a[2*i-1] == 'P') { if(a[2*i] == 'P') { ans = (ans + two[(n-2*i+1)/2] + dt[n/2-i]) % m; } else { ans = (ans + two[(n-2*i)/2] + dt[n/2-i]) % m; } } if(a[2*i-1] == a[2*i]) typ = 1; else typ = 2; } } if(typ%2 == 0 && n%2 && a[n] == 'P') { ans = (ans + 1) % m; } printf("%d\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
2 | Correct | 2 ms | 572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 624 KB | Output is correct |
2 | Correct | 2 ms | 624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 624 KB | Output is correct |
2 | Correct | 2 ms | 624 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 2144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 2560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 3072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 3584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 5504 KB | Output is correct |
2 | Correct | 27 ms | 5504 KB | Output is correct |
3 | Correct | 32 ms | 5516 KB | Output is correct |