Submission #1115418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115418		staszic_ojuz	Snake Escaping (JOI18_snake_escaping)	C++17	12 / 100	640 ms	65536 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
vector<int> tox;
unordered_map<string,int> m;
unordered_map<string,bool> ch;
int l;
int pot(int n)
{
    if(n ==0) return 1;
    return 2*pot(n-1);
}
long long tox_ans(string c)
{
    if(ch[c]) return m[c];
    ch[c] = true;
    string a = c,b = c;
    m[c] = 0;
    bool t = false;
    for(int i = 0;i<l;i++)
    {
        if(c[i] == '?')
        {
            t = true;
            a[i] = '0';
            b[i] = '1';
            m[c] =  tox_ans(a) + tox_ans(b);
            a[i] = '?';
            b[i] = '?';
        }
    }
    if(t) return m[c];
    int ans = 0;
    for(int i = 0;i<l;i++)
    {
        if(c[i] == '1')
        {
            ans+=pot(l-i-1);
        }
    }
    m[c] = tox[ans];
    return tox[ans];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>l;
    int q;
    cin>>q;
    string s;
    cin>>s;
    tox.resize(pot(l));
    for(int i = 0 ;i<pot(l);i++)
    {
        if(s[i] == '0') tox[i] = 0;
        if(s[i] == '1') tox[i] = 1;
        if(s[i] == '2') tox[i] = 2;
        if(s[i] == '3') tox[i] = 3;
        if(s[i] == '4') tox[i] = 4;
        if(s[i] == '5') tox[i] = 5;
        if(s[i] == '6') tox[i] = 6;
        if(s[i] == '7') tox[i] = 7;
        if(s[i] == '8') tox[i] = 8;
        if(s[i] == '9') tox[i] = 9;
    }
    string start;
    for(int i = 0;i<l;i++)
    {
        start += '?';
    }
    int x =tox_ans(start);

    for(int i = 0;i<q;i++)
    {
        string c;
        cin>>c;
        cout<<m[c]<<"\n";
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:72:9: warning: unused variable 'x' [-Wunused-variable]
   72 |     int x =tox_ans(start);
      |         ^

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