제출 #1161774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161774		dragst	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	18 ms	31816 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

long long L, q, id[1000005], a[2000005], b[2000005], c[2000005], ans[1000005];
string s[1000005], val;

bool sortt(long long x, long long y)
{
    long long i;
    for (i=0; i<L; i++)
    {
        if (s[x][i]!=s[y][i]) {return (s[x][i]-'0')<(s[y][i]-'0');};
    };
    return true;
}

void solve(long long x)
{
    long long i, j, k, h, l=0, r=(1LL<<L);
    for (i=0; i<L; i++)
    {
        if (s[id[x]][i]=='0') {r=(l+r)/2;}
        else if (s[id[x]][i]=='1') {l=(l+r)/2;}
        else if ((x==1 || s[id[x]].substr(0, i+1)!=s[id[x-1]].substr(0, i+1)) && i<L-1)
        {
            k=l; h=(l+r)/2;
            for (j=l; j<r; j+=2)
            {
                b[j]=a[k++];
                b[j+1]=a[h++];
            };
            for (j=l; j<r; j++)
            {
                a[j]=b[j];
                if (j==0) {c[j]=a[j];}
                else {c[j]=c[j-1]+a[j];};
            };
        };
    };
    if (l==0) {ans[id[x]]=c[r-1];}
    else {ans[id[x]]=c[r-1]-c[l-1];};
    for (i=L-1; i>=0; i--)
    {
        if (s[id[x]][i]=='0') {r=2*r-l;}
        else if (s[id[x]][i]=='1') {l=2*l-r;}
        else if (s[id[x]][i]=='?' && x<q && s[id[x]].substr(0, i+1)!=s[id[x+1]].substr(0, i+1) && i<L-1)
        {
            k=l; h=(l+r)/2;
            for (j=l; j<r; j+=2)
            {
                b[k++]=a[j];
                b[h++]=a[j+1];
            };
            for (j=l; j<r; j++)
            {
                a[j]=b[j];
                if (j==0) {c[j]=a[j];}
                else {c[j]=c[j-1]+a[j];};
            };
        };
    };
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long i;
    cin >> L >> q >> val;
    for (i=0; i<(1LL<<L); i++)
    {
        a[i]=val[i]-'0';
        if (i==0) {c[i]=a[i];}
        else {c[i]=c[i-1]+a[i];};
    };
    for (i=1; i<=q; i++)
    {
        cin >> s[i];
        id[i]=i;
    };
    sort(id+1, id+q+1, sortt);
    for (i=1; i<=q; i++)
    {
        solve(i);
    };
    for (i=1; i<=q; i++)
    {
        cout << ans[i] << "\n";
    };
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25