Submission #1189279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189279		Boycl07	Prisoner Challenge (IOI22_prison)	C++20	56 / 100	9 ms	1284 KiB

prison

#include "prison.h"

#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const ll LINF = 1e3;
const ll K = 1e2 + 3;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int N = 1e5 + 3;
const int M = 15;
const int LIM = 14348907 + 3;
const ll INF = 1e18;
const int LOG = 12;

int n;

int get_state(int val, int bit)
{
    return 1 + bit + ((val >> bit & 1) ? LOG + 1 : 0);
}

vector<vector<int>> devise_strategy(int N_)
{
    n = N_;
    vector<vector<int>> res(2 * (LOG + 1) + 1, vector<int>(n + 1, 0));
//    cout << 2 * (LOG + 1) + 1 << endl;
    for(int i = 0; i < sz(res); ++i)
    {
        if(i == 0)
        {
            res[i][0] = 0;
            for(int j = 1; j <= n; ++j)
                res[i][j] = get_state(j, LOG);
        }
        else
        {
            int bit;
            int x = 0;
            if(i >= LOG + 2) bit = i - LOG - 2, x = 1;
            else bit = i - 1, x = 0;
            res[i][0] = (bit & 1) ^ !(LOG & 1);
            for(int j = 1; j <= n; ++j)
            {
                int y = j >> bit & 1;
                if(x == y) res[i][j] = (bit ? get_state(j, bit - 1) : 0);
                else
                {
                    if(bit & 1) res[i][j] = (x < y) ? -2 : -1;
                    else res[i][j] = (x < y) ? -1 : -2;
                }
            }
        }
    }
//    for(auto u : res)
//    {
//        for(int v : u) cout << v << " "; cout << endl;
//    }
    return res;
}

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