oj.uz

Submission #80189

# Submission time Handle Problem Language Result Execution time Memory
80189 2018-10-19T13:42:33 Z Bodo171 Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 1977 ms 66560 KB 
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=(1<<20)+5;
char s[nmax];
char t;
int pc[nmax],sub[nmax],supra[nmax],v[nmax];
int l,q,i,j,m0,m1,mq,mn,ans;
bool brk;
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>l>>q;
    cin>>s;
    for(i=0;i<(1<<l);i++)
    {
        if(i!=0)
            pc[i]=pc[(i&(i-1))]+1;
        sub[i]=supra[i]=v[i]=s[i]-'0';
    }
    for(i=0;i<l;i++)
        for(j=0;j<(1<<l);j++)
           if(((1<<i)&j))
              sub[j]+=sub[(j^(1<<i))];
    for(i=0;i<l;i++)
        for(j=(1<<l)-1;j>=0;j--)
           if(!((1<<i)&j))
              supra[j]+=supra[(j^(1<<i))];
    for(int cnt=1;cnt<=q;cnt++)
    {
        cin>>s;
        m0=m1=mq=0;
        for(j=l-1;j>=0;j--)
        {
            t=s[l-1-j];
            if(t=='0') m0+=(1<<j);
            if(t=='1') m1+=(1<<j);
            if(t=='?') mq+=(1<<j);
        }
        mn=min(min(pc[m0],pc[m1]),pc[mq]);
        ans=0;brk=0;
        if(mn==pc[m0])
        {
            ans=supra[m1];
            i=m0;
            while(i!=0)
            {
                if((pc[i]&1)) ans-=supra[(i|m1)];
                else ans+=supra[(i|m1)];
                i=((i-1)&m0);
            }
        }
        else
        {
            if(mn==pc[m1])
            {
                i=m1;
                while(!brk)
                {
                    if(i==0)
                        brk=1;
                    if(((pc[m1]-pc[i])&1)) ans-=sub[(i|mq)];
                    else ans+=sub[(i|mq)];
                    i=((i-1)&m1);
                }
            }
            else
            {
                    i=mq;
                    while(!brk)
                    {
                        ans+=v[(m1|i)];
                        if(i==0)
                            brk=1;
                        i=((i-1)&mq);
                    }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 660 KB Output is correct
10 Correct 4 ms 716 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 660 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 1799 ms 15460 KB Output is correct
12 Correct 1876 ms 20572 KB Output is correct
13 Correct 1841 ms 20572 KB Output is correct
14 Correct 1921 ms 20572 KB Output is correct
15 Correct 1835 ms 20824 KB Output is correct
16 Correct 1859 ms 20824 KB Output is correct
17 Correct 1914 ms 20824 KB Output is correct
18 Correct 1772 ms 21848 KB Output is correct
19 Correct 1882 ms 21848 KB Output is correct
20 Correct 1825 ms 21848 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 660 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 1799 ms 15460 KB Output is correct
12 Correct 1876 ms 20572 KB Output is correct
13 Correct 1841 ms 20572 KB Output is correct
14 Correct 1921 ms 20572 KB Output is correct
15 Correct 1835 ms 20824 KB Output is correct
16 Correct 1859 ms 20824 KB Output is correct
17 Correct 1914 ms 20824 KB Output is correct
18 Correct 1772 ms 21848 KB Output is correct
19 Correct 1882 ms 21848 KB Output is correct
20 Correct 1825 ms 21848 KB Output is correct
21 Correct 1828 ms 34836 KB Output is correct
22 Correct 1886 ms 48616 KB Output is correct
23 Correct 1977 ms 61172 KB Output is correct
24 Runtime error 1975 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.
25 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 660 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Runtime error 226 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 -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 660 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 1799 ms 15460 KB Output is correct
12 Correct 1876 ms 20572 KB Output is correct
13 Correct 1841 ms 20572 KB Output is correct
14 Correct 1921 ms 20572 KB Output is correct
15 Correct 1835 ms 20824 KB Output is correct
16 Correct 1859 ms 20824 KB Output is correct
17 Correct 1914 ms 20824 KB Output is correct
18 Correct 1772 ms 21848 KB Output is correct
19 Correct 1882 ms 21848 KB Output is correct
20 Correct 1825 ms 21848 KB Output is correct
21 Correct 1828 ms 34836 KB Output is correct
22 Correct 1886 ms 48616 KB Output is correct
23 Correct 1977 ms 61172 KB Output is correct
24 Runtime error 1975 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.
25 Halted 0 ms 0 KB -