oj.uz

Submission #255174

# Submission time Handle Problem Language Result Execution time Memory
255174 2020-07-31T13:40:39 Z Atill83 Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 792 ms 65540 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e6;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, l, q;
string s;
ll say[MAXN];
ll say2[MAXN];
ll ans[MAXN];
string qs[MAXN];

const int n37 = 2187;
const int n313 = 1594323;
int child[n313][2];
bool sub[n37][(1<<7)];
ll dp[n313];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>l>>q;

    n = (1<<l);

    cin>>s;

    for(int i = 0; i < q; i++){
        cin>>qs[i];
        for(int j = 0; j < min(l, 7); j++){
            say[i] += (qs[i][j] == '?' ? 2 : qs[i][j] - '0');
            say[i] *= 3;
        }
        say[i] /= 3;
        for(int j = 7; j < l; j++){
            say2[i] += (qs[i][j] == '?' ? 2 : qs[i][j] - '0');
            say2[i] *= 3;
        }
        say2[i] /= 3;
    }

    for(int i = 0; i < n313; i++){
        int cur = i;
        child[i][0] = child[i][1] = -1;
        int cc = 1;
        for(int j = 0; j < 7; j++){
            if(cur % 3 == 2){
                child[i][0] = i - cc;
                child[i][1] = i - 2*cc;
                break;
            }
            cc *= 3;
            cur /= 3;
        }
    }


    for(int i = 0; i < n37; i++){
        for(int j = 0; j < (1<<7); j++){
            int cur1 = i, cur2 = j;
            bool tru = 1;
            for(int k = 0; k < 7; k++){
                if(cur1 % 3 != 2 && cur1 % 3 != cur2 % 2){
                    tru = 0;
                    break;
                }
                cur1 /= 3;
                cur2 /= 2;
            }
            sub[i][j] = tru;
        }
    }

    int rhs = max(0, l - 7);

    for(int j = 0; j < (1<<min(l, 7)); j++){
        
        for(int i = 0; i < n313; i++){
            if(child[i][0] == -1){
                int kal = 0;
                int cur = i;
                for(int k = 0; k < rhs; k++){
                    if(cur % 3) kal += (1<<k);
                    cur /= 3;
                }
                dp[i] = s[(j<<rhs) + kal] - '0';
            }else{
                dp[i] = dp[child[i][0]] + dp[child[i][1]];
            }
        }

        for(int i = 0; i < q; i++){
            if(!sub[say[i]][j]) continue;
            ans[i] += dp[say2[i]];
        }
    }

    for(int i = 0; i < q; i++) 
        cout<<ans[i]<<endl;


    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 56952 KB Output is correct
2 Correct 422 ms 56988 KB Output is correct
3 Correct 426 ms 57080 KB Output is correct
4 Correct 423 ms 56988 KB Output is correct
5 Correct 416 ms 56992 KB Output is correct
6 Correct 434 ms 56992 KB Output is correct
7 Correct 420 ms 57080 KB Output is correct
8 Correct 440 ms 57080 KB Output is correct
9 Correct 410 ms 56952 KB Output is correct
10 Correct 415 ms 57080 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 56952 KB Output is correct
2 Correct 422 ms 56988 KB Output is correct
3 Correct 426 ms 57080 KB Output is correct
4 Correct 423 ms 56988 KB Output is correct
5 Correct 416 ms 56992 KB Output is correct
6 Correct 434 ms 56992 KB Output is correct
7 Correct 420 ms 57080 KB Output is correct
8 Correct 440 ms 57080 KB Output is correct
9 Correct 410 ms 56952 KB Output is correct
10 Correct 415 ms 57080 KB Output is correct
11 Runtime error 194 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 56952 KB Output is correct
2 Correct 422 ms 56988 KB Output is correct
3 Correct 426 ms 57080 KB Output is correct
4 Correct 423 ms 56988 KB Output is correct
5 Correct 416 ms 56992 KB Output is correct
6 Correct 434 ms 56992 KB Output is correct
7 Correct 420 ms 57080 KB Output is correct
8 Correct 440 ms 57080 KB Output is correct
9 Correct 410 ms 56952 KB Output is correct
10 Correct 415 ms 57080 KB Output is correct
11 Runtime error 194 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 56952 KB Output is correct
2 Correct 422 ms 56988 KB Output is correct
3 Correct 426 ms 57080 KB Output is correct
4 Correct 423 ms 56988 KB Output is correct
5 Correct 416 ms 56992 KB Output is correct
6 Correct 434 ms 56992 KB Output is correct
7 Correct 420 ms 57080 KB Output is correct
8 Correct 440 ms 57080 KB Output is correct
9 Correct 410 ms 56952 KB Output is correct
10 Correct 415 ms 57080 KB Output is correct
11 Incorrect 792 ms 63724 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 56952 KB Output is correct
2 Correct 422 ms 56988 KB Output is correct
3 Correct 426 ms 57080 KB Output is correct
4 Correct 423 ms 56988 KB Output is correct
5 Correct 416 ms 56992 KB Output is correct
6 Correct 434 ms 56992 KB Output is correct
7 Correct 420 ms 57080 KB Output is correct
8 Correct 440 ms 57080 KB Output is correct
9 Correct 410 ms 56952 KB Output is correct
10 Correct 415 ms 57080 KB Output is correct
11 Runtime error 194 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -