답안 #80205 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80205	2018-10-19T14:16:59 Z	Bodo171	Snake Escaping (JOI18_snake_escaping)	C++14	65 / 100	2000 ms	53072 KB

snake_escaping

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=(1<<20)+5;
string s;
char t;
char pc[nmax],v[nmax];
int sub[nmax],supra[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;
    getline(cin,s);
    getline(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++)
    {
        getline(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	380 KB	Output is correct
2	Correct	4 ms	500 KB	Output is correct
3	Correct	4 ms	500 KB	Output is correct
4	Correct	4 ms	500 KB	Output is correct
5	Correct	4 ms	516 KB	Output is correct
6	Correct	4 ms	516 KB	Output is correct
7	Correct	4 ms	628 KB	Output is correct
8	Correct	4 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	4 ms	684 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	380 KB	Output is correct
2	Correct	4 ms	500 KB	Output is correct
3	Correct	4 ms	500 KB	Output is correct
4	Correct	4 ms	500 KB	Output is correct
5	Correct	4 ms	516 KB	Output is correct
6	Correct	4 ms	516 KB	Output is correct
7	Correct	4 ms	628 KB	Output is correct
8	Correct	4 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	4 ms	684 KB	Output is correct
11	Correct	1682 ms	4552 KB	Output is correct
12	Correct	1770 ms	5196 KB	Output is correct
13	Correct	1781 ms	5196 KB	Output is correct
14	Correct	1755 ms	5196 KB	Output is correct
15	Correct	1709 ms	5660 KB	Output is correct
16	Correct	1721 ms	5660 KB	Output is correct
17	Correct	1762 ms	5660 KB	Output is correct
18	Correct	1718 ms	6556 KB	Output is correct
19	Correct	1933 ms	6556 KB	Output is correct
20	Correct	1806 ms	6556 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	380 KB	Output is correct
2	Correct	4 ms	500 KB	Output is correct
3	Correct	4 ms	500 KB	Output is correct
4	Correct	4 ms	500 KB	Output is correct
5	Correct	4 ms	516 KB	Output is correct
6	Correct	4 ms	516 KB	Output is correct
7	Correct	4 ms	628 KB	Output is correct
8	Correct	4 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	4 ms	684 KB	Output is correct
11	Correct	1682 ms	4552 KB	Output is correct
12	Correct	1770 ms	5196 KB	Output is correct
13	Correct	1781 ms	5196 KB	Output is correct
14	Correct	1755 ms	5196 KB	Output is correct
15	Correct	1709 ms	5660 KB	Output is correct
16	Correct	1721 ms	5660 KB	Output is correct
17	Correct	1762 ms	5660 KB	Output is correct
18	Correct	1718 ms	6556 KB	Output is correct
19	Correct	1933 ms	6556 KB	Output is correct
20	Correct	1806 ms	6556 KB	Output is correct
21	Correct	1861 ms	6556 KB	Output is correct
22	Correct	1761 ms	6556 KB	Output is correct
23	Correct	1812 ms	6556 KB	Output is correct
24	Correct	1797 ms	6556 KB	Output is correct
25	Correct	1942 ms	20512 KB	Output is correct
26	Correct	1982 ms	32720 KB	Output is correct
27	Execution timed out	2036 ms	32720 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	380 KB	Output is correct
2	Correct	4 ms	500 KB	Output is correct
3	Correct	4 ms	500 KB	Output is correct
4	Correct	4 ms	500 KB	Output is correct
5	Correct	4 ms	516 KB	Output is correct
6	Correct	4 ms	516 KB	Output is correct
7	Correct	4 ms	628 KB	Output is correct
8	Correct	4 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	4 ms	684 KB	Output is correct
11	Correct	168 ms	40736 KB	Output is correct
12	Correct	165 ms	40736 KB	Output is correct
13	Correct	207 ms	40736 KB	Output is correct
14	Correct	184 ms	40736 KB	Output is correct
15	Correct	163 ms	40736 KB	Output is correct
16	Correct	194 ms	40736 KB	Output is correct
17	Correct	181 ms	40736 KB	Output is correct
18	Correct	152 ms	40812 KB	Output is correct
19	Correct	163 ms	40812 KB	Output is correct
20	Correct	163 ms	40812 KB	Output is correct
21	Correct	180 ms	40812 KB	Output is correct
22	Correct	193 ms	40812 KB	Output is correct
23	Correct	164 ms	40812 KB	Output is correct
24	Correct	219 ms	40812 KB	Output is correct
25	Correct	191 ms	40812 KB	Output is correct
26	Correct	151 ms	40812 KB	Output is correct
27	Correct	176 ms	40812 KB	Output is correct
28	Correct	169 ms	40812 KB	Output is correct
29	Correct	174 ms	40812 KB	Output is correct
30	Correct	170 ms	40812 KB	Output is correct
31	Correct	167 ms	40812 KB	Output is correct
32	Correct	199 ms	40812 KB	Output is correct
33	Correct	187 ms	40812 KB	Output is correct
34	Correct	151 ms	40812 KB	Output is correct
35	Correct	187 ms	42608 KB	Output is correct
36	Correct	180 ms	44660 KB	Output is correct
37	Correct	183 ms	46708 KB	Output is correct
38	Correct	188 ms	48904 KB	Output is correct
39	Correct	180 ms	50860 KB	Output is correct
40	Correct	183 ms	53072 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	380 KB	Output is correct
2	Correct	4 ms	500 KB	Output is correct
3	Correct	4 ms	500 KB	Output is correct
4	Correct	4 ms	500 KB	Output is correct
5	Correct	4 ms	516 KB	Output is correct
6	Correct	4 ms	516 KB	Output is correct
7	Correct	4 ms	628 KB	Output is correct
8	Correct	4 ms	628 KB	Output is correct
9	Correct	4 ms	628 KB	Output is correct
10	Correct	4 ms	684 KB	Output is correct
11	Correct	1682 ms	4552 KB	Output is correct
12	Correct	1770 ms	5196 KB	Output is correct
13	Correct	1781 ms	5196 KB	Output is correct
14	Correct	1755 ms	5196 KB	Output is correct
15	Correct	1709 ms	5660 KB	Output is correct
16	Correct	1721 ms	5660 KB	Output is correct
17	Correct	1762 ms	5660 KB	Output is correct
18	Correct	1718 ms	6556 KB	Output is correct
19	Correct	1933 ms	6556 KB	Output is correct
20	Correct	1806 ms	6556 KB	Output is correct
21	Correct	1861 ms	6556 KB	Output is correct
22	Correct	1761 ms	6556 KB	Output is correct
23	Correct	1812 ms	6556 KB	Output is correct
24	Correct	1797 ms	6556 KB	Output is correct
25	Correct	1942 ms	20512 KB	Output is correct
26	Correct	1982 ms	32720 KB	Output is correct
27	Execution timed out	2036 ms	32720 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

답안 #80205

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 53.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
53.0 / 53.0

Subtask #5
0 / 25.0