| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 66791 | 2018-08-12T10:17:05 Z | hamzqq9 | Snake Escaping (JOI18_snake_escaping) | C++14 | 830 ms | 66560 KB |
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 100000000000000
#define MOD 1000000007
#define N 100005
#define MAX 10000006
#define L 14
#define R 6
#define LOG 22
using namespace std;
unsigned short int ans[pw(L)][730];
int val[pw(20)+3];
int po3[12];
int l,q,n;
int res,value;
char s[pw(20)+3];
int get_pos_of_2(int value) {
int cur=0;
while(value) {
if(value%3==2) return cur;
value/=3;
cur++;
}
return -1;
}
int get_val(int bas,int son) {
int cur=0;
for(int i=bas;i<=son;i++) {
cur+=po3[son-i]*(s[i]=='?'?2:(s[i]-'0'));
}
return cur;
}
int get_2_rep(int val) {
int res=0;
int curpw=1;
while(val) {
res+=curpw*(val%3);
curpw*=2;
val/=3;
}
return res;
}
void back_track(int bit,int val) {
if(bit==-1) {
res+=ans[val][value];
return ;
}
if(s[bit]!='?') back_track(bit-1,val+pw(L-1-bit)*(s[bit]=='1'));
else {
back_track(bit-1,val+pw(L-1-bit));
back_track(bit-1,val);
}
}
void pre_calc() {
for(int i=0;i<po3[R];i++) {
int pos=get_pos_of_2(i);
int temp=-1;
if(pos==-1) temp=get_2_rep(i);
for(int j=0;j<pw(L);j++) {
if(pos==-1) {
ans[j][i]=val[temp+pw(R)*j];
}
else {
ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];
}
}
}
}
int main() {
// freopen("input.txt","r",stdin);
scanf("%d %d",&l,&q);
po3[0]=1;
for(int i=1;i<=10;i++) po3[i]=po3[i-1]*3;
n=pw(l);
scanf("%s",s);
for(int i=0;i<n;i++) {
val[i]=s[i]-'0';
}
pre_calc();
while(q--) {
scanf("%s",s+20-l);
for(int i=0;i<20-l;i++) s[i]='0';
res=0;
value=get_val(L,19);
back_track(L-1,0);
printf("%d\n",res);
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 23800 KB | Output is correct |
| 2 | Correct | 159 ms | 23908 KB | Output is correct |
| 3 | Correct | 168 ms | 23908 KB | Output is correct |
| 4 | Correct | 161 ms | 23968 KB | Output is correct |
| 5 | Correct | 157 ms | 24020 KB | Output is correct |
| 6 | Correct | 142 ms | 24020 KB | Output is correct |
| 7 | Correct | 148 ms | 24128 KB | Output is correct |
| 8 | Correct | 132 ms | 24128 KB | Output is correct |
| 9 | Correct | 189 ms | 24128 KB | Output is correct |
| 10 | Correct | 143 ms | 24216 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 23800 KB | Output is correct |
| 2 | Correct | 159 ms | 23908 KB | Output is correct |
| 3 | Correct | 168 ms | 23908 KB | Output is correct |
| 4 | Correct | 161 ms | 23968 KB | Output is correct |
| 5 | Correct | 157 ms | 24020 KB | Output is correct |
| 6 | Correct | 142 ms | 24020 KB | Output is correct |
| 7 | Correct | 148 ms | 24128 KB | Output is correct |
| 8 | Correct | 132 ms | 24128 KB | Output is correct |
| 9 | Correct | 189 ms | 24128 KB | Output is correct |
| 10 | Correct | 143 ms | 24216 KB | Output is correct |
| 11 | Correct | 600 ms | 28304 KB | Output is correct |
| 12 | Correct | 612 ms | 28304 KB | Output is correct |
| 13 | Correct | 522 ms | 28304 KB | Output is correct |
| 14 | Correct | 524 ms | 38052 KB | Output is correct |
| 15 | Correct | 664 ms | 38908 KB | Output is correct |
| 16 | Correct | 549 ms | 48828 KB | Output is correct |
| 17 | Correct | 481 ms | 59620 KB | Output is correct |
| 18 | Runtime error | 830 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. |
| 19 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 23800 KB | Output is correct |
| 2 | Correct | 159 ms | 23908 KB | Output is correct |
| 3 | Correct | 168 ms | 23908 KB | Output is correct |
| 4 | Correct | 161 ms | 23968 KB | Output is correct |
| 5 | Correct | 157 ms | 24020 KB | Output is correct |
| 6 | Correct | 142 ms | 24020 KB | Output is correct |
| 7 | Correct | 148 ms | 24128 KB | Output is correct |
| 8 | Correct | 132 ms | 24128 KB | Output is correct |
| 9 | Correct | 189 ms | 24128 KB | Output is correct |
| 10 | Correct | 143 ms | 24216 KB | Output is correct |
| 11 | Correct | 600 ms | 28304 KB | Output is correct |
| 12 | Correct | 612 ms | 28304 KB | Output is correct |
| 13 | Correct | 522 ms | 28304 KB | Output is correct |
| 14 | Correct | 524 ms | 38052 KB | Output is correct |
| 15 | Correct | 664 ms | 38908 KB | Output is correct |
| 16 | Correct | 549 ms | 48828 KB | Output is correct |
| 17 | Correct | 481 ms | 59620 KB | Output is correct |
| 18 | Runtime error | 830 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. |
| 19 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 23800 KB | Output is correct |
| 2 | Correct | 159 ms | 23908 KB | Output is correct |
| 3 | Correct | 168 ms | 23908 KB | Output is correct |
| 4 | Correct | 161 ms | 23968 KB | Output is correct |
| 5 | Correct | 157 ms | 24020 KB | Output is correct |
| 6 | Correct | 142 ms | 24020 KB | Output is correct |
| 7 | Correct | 148 ms | 24128 KB | Output is correct |
| 8 | Correct | 132 ms | 24128 KB | Output is correct |
| 9 | Correct | 189 ms | 24128 KB | Output is correct |
| 10 | Correct | 143 ms | 24216 KB | Output is correct |
| 11 | Runtime error | 397 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 | 175 ms | 23800 KB | Output is correct |
| 2 | Correct | 159 ms | 23908 KB | Output is correct |
| 3 | Correct | 168 ms | 23908 KB | Output is correct |
| 4 | Correct | 161 ms | 23968 KB | Output is correct |
| 5 | Correct | 157 ms | 24020 KB | Output is correct |
| 6 | Correct | 142 ms | 24020 KB | Output is correct |
| 7 | Correct | 148 ms | 24128 KB | Output is correct |
| 8 | Correct | 132 ms | 24128 KB | Output is correct |
| 9 | Correct | 189 ms | 24128 KB | Output is correct |
| 10 | Correct | 143 ms | 24216 KB | Output is correct |
| 11 | Correct | 600 ms | 28304 KB | Output is correct |
| 12 | Correct | 612 ms | 28304 KB | Output is correct |
| 13 | Correct | 522 ms | 28304 KB | Output is correct |
| 14 | Correct | 524 ms | 38052 KB | Output is correct |
| 15 | Correct | 664 ms | 38908 KB | Output is correct |
| 16 | Correct | 549 ms | 48828 KB | Output is correct |
| 17 | Correct | 481 ms | 59620 KB | Output is correct |
| 18 | Runtime error | 830 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. |
| 19 | Halted | 0 ms | 0 KB | - |