oj.uz

Submission #256759

# Submission time Handle Problem Language Result Execution time Memory
256759 2020-08-03T07:44:50 Z 최은수(#5036) Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 244 ms 17612 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
const int cut=10;
int sum[60000];
int p3[20];
int ans[1000010];
pair<pair<short,short>,int>qid[1000010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int l,q;
    cin>>l>>q;
    string s;
    cin>>s;
    if(l<cut)
    {
        l=cut;
        while((int)s.size()<1<<l)
            s.push_back('0');
    }
    p3[0]=1;
    for(int i=1;i<15;i++)
        p3[i]=p3[i-1]*3;
    for(int i=0;i<q;i++)
    {
        string t;
        cin>>t;
        reverse(all(t));
        while((int)t.size()<l)
            t.push_back('0');
        int id=0;
        for(int j=0;j<cut;j++)
        {
            if(t[j]=='?')
                id+=p3[j]*2;
            else
                id+=((char)t[j]-'0')*p3[j];
        }
        qid[i].se=id;
        int id2=0,id3=0;
        for(int j=cut;j<l;j++)
        {
            if(t[j]=='?')
                id3+=1<<(j-cut);
            else
                id2+=((char)t[j]-'0')*(1<<(j-cut));
        }
        qid[i].fi.fi=id2;
        qid[i].fi.se=id3;
    }
    for(int i=0;i<1<<(l-cut);i++)
    {
        vector<int>v;
        for(int i=0;i<1<<l;i++)
        {
            int id=0;
            for(int j=0;j<l;j++)
                id+=(i>>j&1)*p3[j];
            sum[id]=(char)s[i]-'0';
            v.eb(id);
        }
        for(int i=0;i<l;i++)
        {
            for(int k=0,m=v.size();k<m;k++)
            {
                int j=v[k];
                int cut=j%p3[i+1]/p3[i];
                sum[j+(2-cut)*p3[i]]+=sum[j];
                if(cut==1)
                    v.eb(j+p3[i]);
            }
        }
        for(int j=0;j<q;j++)
            if(((qid[j].fi.fi^i)&~qid[j].fi.se)==0)
                ans[j]+=sum[qid[j].se];
        for(int&t:v)
            sum[t]=0;
    }
    for(int i=0;i<q;i++)
        cout<<ans[i]<<'\n';
    cout.flush();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 244 ms 16516 KB Output is correct
12 Correct 234 ms 16128 KB Output is correct
13 Correct 213 ms 15364 KB Output is correct
14 Correct 216 ms 15452 KB Output is correct
15 Correct 232 ms 16452 KB Output is correct
16 Correct 225 ms 15620 KB Output is correct
17 Correct 227 ms 15620 KB Output is correct
18 Correct 182 ms 17612 KB Output is correct
19 Correct 183 ms 14468 KB Output is correct
20 Correct 235 ms 16132 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 244 ms 16516 KB Output is correct
12 Correct 234 ms 16128 KB Output is correct
13 Correct 213 ms 15364 KB Output is correct
14 Correct 216 ms 15452 KB Output is correct
15 Correct 232 ms 16452 KB Output is correct
16 Correct 225 ms 15620 KB Output is correct
17 Correct 227 ms 15620 KB Output is correct
18 Correct 182 ms 17612 KB Output is correct
19 Correct 183 ms 14468 KB Output is correct
20 Correct 235 ms 16132 KB Output is correct
21 Runtime error 177 ms 16524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Runtime error 21 ms 5796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 244 ms 16516 KB Output is correct
12 Correct 234 ms 16128 KB Output is correct
13 Correct 213 ms 15364 KB Output is correct
14 Correct 216 ms 15452 KB Output is correct
15 Correct 232 ms 16452 KB Output is correct
16 Correct 225 ms 15620 KB Output is correct
17 Correct 227 ms 15620 KB Output is correct
18 Correct 182 ms 17612 KB Output is correct
19 Correct 183 ms 14468 KB Output is correct
20 Correct 235 ms 16132 KB Output is correct
21 Runtime error 177 ms 16524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -