oj.uz

Submission #256764

# Submission time Handle Problem Language Result Execution time Memory
256764 2020-08-03T07:47:09 Z 최은수(#5036) Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 1973 ms 17540 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 j=0;j<1<<cut;j++)
        {
            int id=0;
            for(int k=0;k<cut;k++)
                id+=(j>>k&1)*p3[k];
            sum[id]=(char)s[j]-'0';
            v.eb(id);
        }
        for(int li=0;li<cut;li++)
        {
            for(int k=0,m=v.size();k<m;k++)
            {
                int j=v[k];
                int cut=j%p3[li+1]/p3[li];
                sum[j+(2-cut)*p3[li]]+=sum[j];
                if(cut==1)
                    v.eb(j+p3[li]);
            }
        }
        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 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 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 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 247 ms 16516 KB Output is correct
12 Correct 248 ms 16388 KB Output is correct
13 Correct 219 ms 15404 KB Output is correct
14 Correct 220 ms 15620 KB Output is correct
15 Correct 229 ms 16516 KB Output is correct
16 Correct 233 ms 15996 KB Output is correct
17 Correct 233 ms 15748 KB Output is correct
18 Correct 189 ms 17540 KB Output is correct
19 Correct 192 ms 14464 KB Output is correct
20 Correct 279 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 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 247 ms 16516 KB Output is correct
12 Correct 248 ms 16388 KB Output is correct
13 Correct 219 ms 15404 KB Output is correct
14 Correct 220 ms 15620 KB Output is correct
15 Correct 229 ms 16516 KB Output is correct
16 Correct 233 ms 15996 KB Output is correct
17 Correct 233 ms 15748 KB Output is correct
18 Correct 189 ms 17540 KB Output is correct
19 Correct 192 ms 14464 KB Output is correct
20 Correct 279 ms 16132 KB Output is correct
21 Incorrect 300 ms 16560 KB Output isn't correct
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 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Incorrect 1973 ms 3012 KB Output isn't correct
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 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 247 ms 16516 KB Output is correct
12 Correct 248 ms 16388 KB Output is correct
13 Correct 219 ms 15404 KB Output is correct
14 Correct 220 ms 15620 KB Output is correct
15 Correct 229 ms 16516 KB Output is correct
16 Correct 233 ms 15996 KB Output is correct
17 Correct 233 ms 15748 KB Output is correct
18 Correct 189 ms 17540 KB Output is correct
19 Correct 192 ms 14464 KB Output is correct
20 Correct 279 ms 16132 KB Output is correct
21 Incorrect 300 ms 16560 KB Output isn't correct
22 Halted 0 ms 0 KB -