Submission #966143

#	Time	Username	Problem	Language	Result	Execution time	Memory
966143		andrej246	Prisoner Challenge (IOI22_prison)	C++17	48.50 / 100	14 ms	1372 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

#define NL '\n'
#define EL cout << NL
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define FORS(i,s,n) for(int i = (s); i < (n); i++)
#define PRINTV(v) for(auto a:v) {cout << a << " ";} EL;
#define PRINTVV(v) for(auto a:v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
#define STRP(p) "{" << (p).f << "," << (p).s << "}"
#define PRINTVP(v) for(auto a:v) {cout << STRP(a) << " ";} EL;
#define PRINTVVP(v) for(auto a:v) {PRINTVP(a);}

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

vl pwr;

ll get_trit(ll k, ll n) { // kth least significant trit
    n %= pwr[k+1];
    return n/pwr[k];
}

std::vector<std::vector<int>> devise_strategy(int N) {
    pwr.push_back(1);
    while(pwr.back() <= N) pwr.push_back(3*pwr.back());
    ll mpow = pwr.size()-1;
    ll x = mpow*4-1;
    vector<vector<int>> strat(x+1,vector<int>(N+1));
    FOR(st,mpow) {
        strat[st*4][0] = 0;
        FORS(i,1,N+1) {
            strat[st*4][i] = st*4+1+get_trit(mpow-st-1,i);
        }
        FORS(t,0,3) {
            strat[st*4+t+1][0] = 1;
            FORS(i,1,N+1) {
                ll t2 = get_trit(mpow-st-1,i);
                if (t == t2) strat[st*4+t+1][i] = min((ll)st*4+4,x);
                if (t < t2) strat[st*4+t+1][i] = -1;
                if (t > t2) strat[st*4+t+1][i] = -2;
            }
        }
    }
    //cout << x << NL;
    return strat;
}

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