oj.uz

Submission #80188

# Submission time Handle Problem Language Result Execution time Memory
80188 2018-10-19T13:40:15 Z Bodo171 Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 1867 ms 66560 KB 
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=(1<<20)+5;
string s;
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 5 ms 376 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 4 ms 520 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 520 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 4 ms 584 KB Output is correct
10 Correct 4 ms 584 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 4 ms 520 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 520 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 4 ms 584 KB Output is correct
10 Correct 4 ms 584 KB Output is correct
11 Correct 1867 ms 15432 KB Output is correct
12 Correct 1820 ms 23236 KB Output is correct
13 Correct 1776 ms 23236 KB Output is correct
14 Correct 1804 ms 23236 KB Output is correct
15 Correct 1754 ms 23668 KB Output is correct
16 Correct 1776 ms 23668 KB Output is correct
17 Correct 1791 ms 33464 KB Output is correct
18 Correct 1770 ms 45988 KB Output is correct
19 Correct 1725 ms 53644 KB Output is correct
20 Runtime error 1763 ms 65760 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.

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 4 ms 520 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 520 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 4 ms 584 KB Output is correct
10 Correct 4 ms 584 KB Output is correct
11 Correct 1867 ms 15432 KB Output is correct
12 Correct 1820 ms 23236 KB Output is correct
13 Correct 1776 ms 23236 KB Output is correct
14 Correct 1804 ms 23236 KB Output is correct
15 Correct 1754 ms 23668 KB Output is correct
16 Correct 1776 ms 23668 KB Output is correct
17 Correct 1791 ms 33464 KB Output is correct
18 Correct 1770 ms 45988 KB Output is correct
19 Correct 1725 ms 53644 KB Output is correct
20 Runtime error 1763 ms 65760 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.

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 4 ms 520 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 520 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 4 ms 584 KB Output is correct
10 Correct 4 ms 584 KB Output is correct
11 Runtime error 184 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 5 ms 376 KB Output is correct
2 Correct 4 ms 520 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 4 ms 520 KB Output is correct
5 Correct 4 ms 520 KB Output is correct
6 Correct 4 ms 520 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 4 ms 584 KB Output is correct
10 Correct 4 ms 584 KB Output is correct
11 Correct 1867 ms 15432 KB Output is correct
12 Correct 1820 ms 23236 KB Output is correct
13 Correct 1776 ms 23236 KB Output is correct
14 Correct 1804 ms 23236 KB Output is correct
15 Correct 1754 ms 23668 KB Output is correct
16 Correct 1776 ms 23668 KB Output is correct
17 Correct 1791 ms 33464 KB Output is correct
18 Correct 1770 ms 45988 KB Output is correct
19 Correct 1725 ms 53644 KB Output is correct
20 Runtime error 1763 ms 65760 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.