답안 #80202 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80202	2018-10-19T14:12:57 Z	Bodo171	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	1980 ms	66560 KB

snake_escaping

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	420 KB	Output is correct
2	Correct	4 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	4 ms	540 KB	Output is correct
5	Correct	5 ms	540 KB	Output is correct
6	Correct	4 ms	696 KB	Output is correct
7	Correct	4 ms	736 KB	Output is correct
8	Correct	4 ms	736 KB	Output is correct
9	Correct	4 ms	736 KB	Output is correct
10	Correct	4 ms	736 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	420 KB	Output is correct
2	Correct	4 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	4 ms	540 KB	Output is correct
5	Correct	5 ms	540 KB	Output is correct
6	Correct	4 ms	696 KB	Output is correct
7	Correct	4 ms	736 KB	Output is correct
8	Correct	4 ms	736 KB	Output is correct
9	Correct	4 ms	736 KB	Output is correct
10	Correct	4 ms	736 KB	Output is correct
11	Correct	1785 ms	15560 KB	Output is correct
12	Correct	1743 ms	23156 KB	Output is correct
13	Correct	1790 ms	23156 KB	Output is correct
14	Correct	1769 ms	23156 KB	Output is correct
15	Correct	1852 ms	23484 KB	Output is correct
16	Correct	1895 ms	23484 KB	Output is correct
17	Correct	1872 ms	23484 KB	Output is correct
18	Correct	1740 ms	24352 KB	Output is correct
19	Correct	1749 ms	24352 KB	Output is correct
20	Correct	1832 ms	24352 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	420 KB	Output is correct
2	Correct	4 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	4 ms	540 KB	Output is correct
5	Correct	5 ms	540 KB	Output is correct
6	Correct	4 ms	696 KB	Output is correct
7	Correct	4 ms	736 KB	Output is correct
8	Correct	4 ms	736 KB	Output is correct
9	Correct	4 ms	736 KB	Output is correct
10	Correct	4 ms	736 KB	Output is correct
11	Correct	1785 ms	15560 KB	Output is correct
12	Correct	1743 ms	23156 KB	Output is correct
13	Correct	1790 ms	23156 KB	Output is correct
14	Correct	1769 ms	23156 KB	Output is correct
15	Correct	1852 ms	23484 KB	Output is correct
16	Correct	1895 ms	23484 KB	Output is correct
17	Correct	1872 ms	23484 KB	Output is correct
18	Correct	1740 ms	24352 KB	Output is correct
19	Correct	1749 ms	24352 KB	Output is correct
20	Correct	1832 ms	24352 KB	Output is correct
21	Correct	1928 ms	32848 KB	Output is correct
22	Correct	1854 ms	33132 KB	Output is correct
23	Correct	1931 ms	33132 KB	Output is correct
24	Correct	1980 ms	33132 KB	Output is correct
25	Correct	1845 ms	47596 KB	Output is correct
26	Correct	1942 ms	59960 KB	Output is correct
27	Runtime error	1932 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.
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	420 KB	Output is correct
2	Correct	4 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	4 ms	540 KB	Output is correct
5	Correct	5 ms	540 KB	Output is correct
6	Correct	4 ms	696 KB	Output is correct
7	Correct	4 ms	736 KB	Output is correct
8	Correct	4 ms	736 KB	Output is correct
9	Correct	4 ms	736 KB	Output is correct
10	Correct	4 ms	736 KB	Output is correct
11	Runtime error	171 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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	420 KB	Output is correct
2	Correct	4 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	4 ms	540 KB	Output is correct
5	Correct	5 ms	540 KB	Output is correct
6	Correct	4 ms	696 KB	Output is correct
7	Correct	4 ms	736 KB	Output is correct
8	Correct	4 ms	736 KB	Output is correct
9	Correct	4 ms	736 KB	Output is correct
10	Correct	4 ms	736 KB	Output is correct
11	Correct	1785 ms	15560 KB	Output is correct
12	Correct	1743 ms	23156 KB	Output is correct
13	Correct	1790 ms	23156 KB	Output is correct
14	Correct	1769 ms	23156 KB	Output is correct
15	Correct	1852 ms	23484 KB	Output is correct
16	Correct	1895 ms	23484 KB	Output is correct
17	Correct	1872 ms	23484 KB	Output is correct
18	Correct	1740 ms	24352 KB	Output is correct
19	Correct	1749 ms	24352 KB	Output is correct
20	Correct	1832 ms	24352 KB	Output is correct
21	Correct	1928 ms	32848 KB	Output is correct
22	Correct	1854 ms	33132 KB	Output is correct
23	Correct	1931 ms	33132 KB	Output is correct
24	Correct	1980 ms	33132 KB	Output is correct
25	Correct	1845 ms	47596 KB	Output is correct
26	Correct	1942 ms	59960 KB	Output is correct
27	Runtime error	1932 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.
28	Halted	0 ms	0 KB	-

답안 #80202

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0