oj.uz

Submission #1115409

# Submission time Handle Problem Language Result Execution time Memory
1115409 2024-11-20T12:45:40 Z staszic_ojuz Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 2000 ms 1352 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> tox;
unordered_map<string,int> m;
int l;
int pot(int n)
{
    if(n ==0) return 1;
    return 2*pot(n-1);
}
long long tox_ans(string c)
{
    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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1352 KB Time limit exceeded
2 Halted 0 ms 0 KB -