| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 67176 | 2018-08-13T13:18:59 Z | ekrem | Snake Escaping (JOI18_snake_escaping) | C++ | 1129 ms | 66560 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1600005
using namespace std;
int n, m, a[(1<<20)+10], dp[N], prec[N], cvp[1000005], kaps[3000][200];
char s[N], c;
pair < int , int > q[1000005];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
for(int i = 0; i < 1594323; i++){
int x = i, crp = 1, ckr = -1, say = 0, bit = 0;
while(x){
if(x%3 == 2){
ckr = crp;
break;
}
bit += (1<<say)*(x%3);
say++;
crp *= 3;
x /= 3;
}
if(ckr == -1)
prec[i] = -bit;
else
prec[i] = ckr;
}
scanf("%d %d %s",&n ,&m, s);
for(int i = 0; i < (1<<n); i++)
a[i] = s[i] - '0';
for(int i = 1; i <= m; i++){
int say = 0, son = 0, crp = 1;
long long bit = 0;
scanf("%s",s + 1);
for(int i = 1; i <= n; i++){
bit *= 3;
bit += (s[i] == '?') ? 2 : s[i] - '0';
}
for(int say = 1; say <= 13; say++){
son += crp*(bit%3);
crp *= 3;
bit/=3;
}
// cout << bit << " , " << son << endl;
q[i] = mp(bit, son);
}
for(int i = 0; i < 2187; i++)
for(int j = 0; j < (1<<7); j++){
if(i == 0 and j == 0)
kaps[i][j] = 1;
else if(i%3 != 2 and i%3 != j%2)
kaps[i][j] = 0;
else
kaps[i][j] = kaps[i/3][j/2];
}
for(int i = 0; i < (1<<7); i++){
for(int j = 0; j < 1594323; j++){
if(prec[j] <= 0)
dp[j] = a[i*(1<<13) - prec[j]];
else
dp[j] = dp[j - prec[j]] + dp[j - prec[j]*2];
}
for(int j = 1; j <= m; j++){
if(kaps[q[j].st ][i ] ){
cvp[j] += dp[q[j].nd];
}
}
}
for(int i = 1; i <= m; i++)
printf("%d\n",cvp[i]);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 403 ms | 14716 KB | Output is correct |
| 2 | Correct | 434 ms | 14716 KB | Output is correct |
| 3 | Correct | 413 ms | 14780 KB | Output is correct |
| 4 | Correct | 464 ms | 14872 KB | Output is correct |
| 5 | Correct | 416 ms | 14872 KB | Output is correct |
| 6 | Correct | 402 ms | 14888 KB | Output is correct |
| 7 | Correct | 398 ms | 14888 KB | Output is correct |
| 8 | Correct | 433 ms | 14888 KB | Output is correct |
| 9 | Correct | 401 ms | 14888 KB | Output is correct |
| 10 | Correct | 418 ms | 15012 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 403 ms | 14716 KB | Output is correct |
| 2 | Correct | 434 ms | 14716 KB | Output is correct |
| 3 | Correct | 413 ms | 14780 KB | Output is correct |
| 4 | Correct | 464 ms | 14872 KB | Output is correct |
| 5 | Correct | 416 ms | 14872 KB | Output is correct |
| 6 | Correct | 402 ms | 14888 KB | Output is correct |
| 7 | Correct | 398 ms | 14888 KB | Output is correct |
| 8 | Correct | 433 ms | 14888 KB | Output is correct |
| 9 | Correct | 401 ms | 14888 KB | Output is correct |
| 10 | Correct | 418 ms | 15012 KB | Output is correct |
| 11 | Correct | 1008 ms | 34968 KB | Output is correct |
| 12 | Correct | 1129 ms | 35912 KB | Output is correct |
| 13 | Correct | 940 ms | 35912 KB | Output is correct |
| 14 | Correct | 896 ms | 42160 KB | Output is correct |
| 15 | Correct | 913 ms | 43176 KB | Output is correct |
| 16 | Correct | 1111 ms | 43176 KB | Output is correct |
| 17 | Correct | 970 ms | 43176 KB | Output is correct |
| 18 | Correct | 1016 ms | 44576 KB | Output is correct |
| 19 | Correct | 817 ms | 44576 KB | Output is correct |
| 20 | Correct | 876 ms | 45596 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 403 ms | 14716 KB | Output is correct |
| 2 | Correct | 434 ms | 14716 KB | Output is correct |
| 3 | Correct | 413 ms | 14780 KB | Output is correct |
| 4 | Correct | 464 ms | 14872 KB | Output is correct |
| 5 | Correct | 416 ms | 14872 KB | Output is correct |
| 6 | Correct | 402 ms | 14888 KB | Output is correct |
| 7 | Correct | 398 ms | 14888 KB | Output is correct |
| 8 | Correct | 433 ms | 14888 KB | Output is correct |
| 9 | Correct | 401 ms | 14888 KB | Output is correct |
| 10 | Correct | 418 ms | 15012 KB | Output is correct |
| 11 | Correct | 1008 ms | 34968 KB | Output is correct |
| 12 | Correct | 1129 ms | 35912 KB | Output is correct |
| 13 | Correct | 940 ms | 35912 KB | Output is correct |
| 14 | Correct | 896 ms | 42160 KB | Output is correct |
| 15 | Correct | 913 ms | 43176 KB | Output is correct |
| 16 | Correct | 1111 ms | 43176 KB | Output is correct |
| 17 | Correct | 970 ms | 43176 KB | Output is correct |
| 18 | Correct | 1016 ms | 44576 KB | Output is correct |
| 19 | Correct | 817 ms | 44576 KB | Output is correct |
| 20 | Correct | 876 ms | 45596 KB | Output is correct |
| 21 | Correct | 915 ms | 45848 KB | Output is correct |
| 22 | Correct | 964 ms | 54168 KB | Output is correct |
| 23 | Correct | 1004 ms | 60520 KB | Output is correct |
| 24 | Correct | 970 ms | 60520 KB | Output is correct |
| 25 | Runtime error | 995 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 26 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 403 ms | 14716 KB | Output is correct |
| 2 | Correct | 434 ms | 14716 KB | Output is correct |
| 3 | Correct | 413 ms | 14780 KB | Output is correct |
| 4 | Correct | 464 ms | 14872 KB | Output is correct |
| 5 | Correct | 416 ms | 14872 KB | Output is correct |
| 6 | Correct | 402 ms | 14888 KB | Output is correct |
| 7 | Correct | 398 ms | 14888 KB | Output is correct |
| 8 | Correct | 433 ms | 14888 KB | Output is correct |
| 9 | Correct | 401 ms | 14888 KB | Output is correct |
| 10 | Correct | 418 ms | 15012 KB | Output is correct |
| 11 | Runtime error | 475 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 12 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 403 ms | 14716 KB | Output is correct |
| 2 | Correct | 434 ms | 14716 KB | Output is correct |
| 3 | Correct | 413 ms | 14780 KB | Output is correct |
| 4 | Correct | 464 ms | 14872 KB | Output is correct |
| 5 | Correct | 416 ms | 14872 KB | Output is correct |
| 6 | Correct | 402 ms | 14888 KB | Output is correct |
| 7 | Correct | 398 ms | 14888 KB | Output is correct |
| 8 | Correct | 433 ms | 14888 KB | Output is correct |
| 9 | Correct | 401 ms | 14888 KB | Output is correct |
| 10 | Correct | 418 ms | 15012 KB | Output is correct |
| 11 | Correct | 1008 ms | 34968 KB | Output is correct |
| 12 | Correct | 1129 ms | 35912 KB | Output is correct |
| 13 | Correct | 940 ms | 35912 KB | Output is correct |
| 14 | Correct | 896 ms | 42160 KB | Output is correct |
| 15 | Correct | 913 ms | 43176 KB | Output is correct |
| 16 | Correct | 1111 ms | 43176 KB | Output is correct |
| 17 | Correct | 970 ms | 43176 KB | Output is correct |
| 18 | Correct | 1016 ms | 44576 KB | Output is correct |
| 19 | Correct | 817 ms | 44576 KB | Output is correct |
| 20 | Correct | 876 ms | 45596 KB | Output is correct |
| 21 | Correct | 915 ms | 45848 KB | Output is correct |
| 22 | Correct | 964 ms | 54168 KB | Output is correct |
| 23 | Correct | 1004 ms | 60520 KB | Output is correct |
| 24 | Correct | 970 ms | 60520 KB | Output is correct |
| 25 | Runtime error | 995 ms | 66560 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 26 | Halted | 0 ms | 0 KB | - |