답안 #80206 :: oj.uz

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

snake_escaping

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=(1<<20)+5;
string s,str;
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,str);
    getline(cin,str);
    for(i=0;i<(1<<l);i++)
    {
        if(i!=0)
            pc[i]=pc[(i&(i-1))]+1;
        sub[i]=supra[i]=v[i]=str[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	376 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	6 ms	508 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	4 ms	680 KB	Output is correct
10	Correct	5 ms	680 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	6 ms	508 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	4 ms	680 KB	Output is correct
10	Correct	5 ms	680 KB	Output is correct
11	Correct	1795 ms	4536 KB	Output is correct
12	Correct	1760 ms	4536 KB	Output is correct
13	Correct	1848 ms	4536 KB	Output is correct
14	Correct	1955 ms	4536 KB	Output is correct
15	Correct	1801 ms	4732 KB	Output is correct
16	Correct	1745 ms	4732 KB	Output is correct
17	Correct	1821 ms	4732 KB	Output is correct
18	Correct	1716 ms	5656 KB	Output is correct
19	Correct	1749 ms	5656 KB	Output is correct
20	Correct	1708 ms	5656 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	6 ms	508 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	4 ms	680 KB	Output is correct
10	Correct	5 ms	680 KB	Output is correct
11	Correct	1795 ms	4536 KB	Output is correct
12	Correct	1760 ms	4536 KB	Output is correct
13	Correct	1848 ms	4536 KB	Output is correct
14	Correct	1955 ms	4536 KB	Output is correct
15	Correct	1801 ms	4732 KB	Output is correct
16	Correct	1745 ms	4732 KB	Output is correct
17	Correct	1821 ms	4732 KB	Output is correct
18	Correct	1716 ms	5656 KB	Output is correct
19	Correct	1749 ms	5656 KB	Output is correct
20	Correct	1708 ms	5656 KB	Output is correct
21	Correct	1763 ms	5656 KB	Output is correct
22	Correct	1837 ms	5656 KB	Output is correct
23	Correct	1883 ms	5656 KB	Output is correct
24	Correct	1952 ms	5656 KB	Output is correct
25	Correct	1951 ms	5808 KB	Output is correct
26	Correct	1875 ms	5808 KB	Output is correct
27	Correct	1932 ms	5808 KB	Output is correct
28	Correct	1698 ms	20500 KB	Output is correct
29	Correct	1783 ms	30284 KB	Output is correct
30	Correct	1892 ms	45948 KB	Output is correct
31	Correct	1855 ms	59548 KB	Output is correct
32	Runtime error	1924 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.
33	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	6 ms	508 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	4 ms	680 KB	Output is correct
10	Correct	5 ms	680 KB	Output is correct
11	Runtime error	170 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	376 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	6 ms	508 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	4 ms	680 KB	Output is correct
10	Correct	5 ms	680 KB	Output is correct
11	Correct	1795 ms	4536 KB	Output is correct
12	Correct	1760 ms	4536 KB	Output is correct
13	Correct	1848 ms	4536 KB	Output is correct
14	Correct	1955 ms	4536 KB	Output is correct
15	Correct	1801 ms	4732 KB	Output is correct
16	Correct	1745 ms	4732 KB	Output is correct
17	Correct	1821 ms	4732 KB	Output is correct
18	Correct	1716 ms	5656 KB	Output is correct
19	Correct	1749 ms	5656 KB	Output is correct
20	Correct	1708 ms	5656 KB	Output is correct
21	Correct	1763 ms	5656 KB	Output is correct
22	Correct	1837 ms	5656 KB	Output is correct
23	Correct	1883 ms	5656 KB	Output is correct
24	Correct	1952 ms	5656 KB	Output is correct
25	Correct	1951 ms	5808 KB	Output is correct
26	Correct	1875 ms	5808 KB	Output is correct
27	Correct	1932 ms	5808 KB	Output is correct
28	Correct	1698 ms	20500 KB	Output is correct
29	Correct	1783 ms	30284 KB	Output is correct
30	Correct	1892 ms	45948 KB	Output is correct
31	Correct	1855 ms	59548 KB	Output is correct
32	Runtime error	1924 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.
33	Halted	0 ms	0 KB	-

답안 #80206

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