oj.uz

Submission #950817

# Submission time Handle Problem Language Result Execution time Memory
950817 2024-03-20T18:14:28 Z Dec0Dedd Prisoner Challenge (IOI22_prison) C++17
56 / 100
 14 ms 1300 KB 
#include <bits/stdc++.h>
#include "prison.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int K = 13;

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> res(2*K+1, vector<int>(n+1, 0));

    // 2*i+1 - ith bit set
    // 2*i+2 - ith bit not set

    // for i=0, 2, 4, ... we check in A
    // for i=1, 3, 5, ... we check in B

    res[0][0]=(K-1)%2;
    for (int i=1; i<=n; ++i) {
        int x=K-1;
        if (i&(1<<x)) res[0][i]=2*x+1;
        else res[0][i]=2*x+2;
    }

    for (int i=0; i<K; ++i) {
        int s=2*i+1;

        if (i%2 == 0) {
            res[s][0]=1; // we know ith bit of A so we need to check B
            for (int j=1; j<=n; ++j) {
                if (j&(1<<i)) {
                    int x=i-1;
                    if (j&(1<<x)) res[s][j]=2*x+1;
                    else res[s][j]=2*x+2;
                } else res[s][j]=-2;
            }
        } else {
            res[s][0]=0;
            for (int j=1; j<=n; ++j) {
                if (j&(1<<i)) {
                    int x=i-1;
                    if (j&(1<<x)) res[s][j]=2*x+1;
                    else res[s][j]=2*x+2;
                } else res[s][j]=-1;
            }
        }

        s=2*i+2;
        if (i%2 == 0) {
            res[s][0]=1;
            for (int j=1; j<=n; ++j) {
                if (j&(1<<i)) res[s][j]=-1;
                else {
                    int x=i-1;
                    if (j&(1<<x)) res[s][j]=2*x+1;
                    else res[s][j]=2*x+2;
                }
            }
        } else {
            res[s][0]=0;
            for (int j=1; j<=n; ++j) {
                if (j&(1<<i)) res[s][j]=-2;
                else {
                    int x=i-1;
                    if (j&(1<<x)) res[s][j]=2*x+1;
                    else res[s][j]=2*x+2;
                }
            }
        }
    }

    //cout<<"size "<<res.size()<<"\n";
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
46.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Partially correct 0 ms 352 KB Output is partially correct
3 Partially correct 0 ms 384 KB Output is partially correct
4 Partially correct 5 ms 600 KB Output is partially correct
5 Partially correct 9 ms 1116 KB Output is partially correct
6 Partially correct 11 ms 1300 KB Output is partially correct
7 Partially correct 14 ms 1108 KB Output is partially correct
8 Partially correct 1 ms 352 KB Output is partially correct
9 Partially correct 1 ms 348 KB Output is partially correct
10 Partially correct 2 ms 352 KB Output is partially correct
11 Partially correct 5 ms 776 KB Output is partially correct
12 Partially correct 9 ms 1116 KB Output is partially correct