Submission #832445

#	Time	Username	Problem	Language	Result	Execution time	Memory
832445		fatemetmhr	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	15 ms	1652 KiB

prison

// komak!

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const ll mod   = 1e9 + 7;
const int maxn5 = 1e5 + 10;

int bt[maxn5][20];

std::vector<std::vector<int>> devise_strategy(int n) {

    for(int i = 1; i <= n; i++){
        int pt = 0, x = i;
        while(x){
            bt[i][pt] = x % 2;
            pt++;
            x /= 2;
        }
    }

    vector <vector <int>> ret;
    int x = 24;
    ret.resize(x);
    ret[0].pb(1);
    for(int i = 1; i <= n; i++){
        ret[0].pb(5 * 4 + bt[i][11] + bt[i][12] * 2);
    }
    for(int tt = 1; tt < x; tt++){
        int i = tt - 1;
        int bl = i / 4, pre = i % 4;
        ret[tt].pb((bl % 2) ^ 1);
        for(int j = 1; j <= n; j++){
            int cur = bt[j][bl * 2 + 1] + bt[j][bl * 2 + 2] * 2;
            if(pre < cur)
                ret[tt].pb(-((ret[tt][0] ^ 1) + 1));
            else if(pre > cur)
                ret[tt].pb(-((ret[tt][0]) + 1));
            else{
                if(bl)
                    ret[tt].pb(4 * (bl - 1) + bt[j][(bl - 1) * 2 + 1] + bt[j][(bl - 1) * 2 + 2] * 2);
                else
                    ret[tt].pb((j & 1) ? -1 : -2);
            }

        }
    }
    for(int i = 0; i < int(ret.size()); i++) for(int j = 1; j < int(ret[i].size()); j++)
        if(ret[i][j] >= 0)
            ret[i][j]++;
    return ret;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 62 / 90