Submission #832978

#	Time	Username	Problem	Language	Result	Execution time	Memory
832978		fatemetmhr	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	11 ms	1620 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 = 23;
    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 i = 1; i < x; i++){
        int bl = i / 4, pre = i % 4;
        ret[i].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(!bl){
                cur += (j & 1);
                if(j % 8 == 0)
                    ret[i].pb(-((ret[i][0]) + 1));
                else if(j % 8 == 7)
                    ret[i].pb(-((ret[i][0] ^ 1) + 1));
                else if(pre < cur)
                    ret[i].pb(-((ret[i][0] ^ 1) + 1));
                else if(pre > cur)
                    ret[i].pb(-((ret[i][0]) + 1));
                else
                    ret[i].pb((j & 1) ? -2 : -1);
                continue;
            }
            if(pre < cur)
                ret[i].pb(-((ret[i][0] ^ 1) + 1));
            else if(pre > cur)
                ret[i].pb(-((ret[i][0]) + 1));
            else{
                if(bl == 1){
                    if(j % 8 == 0)
                        ret[i].pb(-((ret[i][0]) + 1));
                    else if(j % 8 == 7)
                        ret[i].pb(-((ret[i][0] ^ 1) + 1));
                    else
                        ret[i].pb(4 * (bl - 1) + bt[j][(bl - 1) * 2 + 1] + bt[j][(bl - 1) * 2 + 2] * 2 + (j % 2));
                }
                else
                    ret[i].pb(4 * (bl - 1) + bt[j][(bl - 1) * 2 + 1] + bt[j][(bl - 1) * 2 + 2] * 2);
            }
        }
    }
    return ret;
}

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