Submission #812145

#	Time	Username	Problem	Language	Result	Execution time	Memory
812145		blackyuki	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1108 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;

std::vector<std::vector<int>> devise_strategy(int N){
    vi tmp={2,3,3,3,3,2,2,2,2};
    vi tmp2={5022,2510,836,278,92,30,14,6,2};
    auto f=[&](ll x,ll i){
        rep(j,i)x=(x-1)%tmp2[j+1];
        if(x==0)return -1ll;
        if(x==tmp2[i]-1)return -2ll;
        return (x-1)/(tmp2[i+1]);
    };
    vector<vector<int>> res(1);
    res[0].pb(0);
    ll m=1;
    {
        rep(j,N){
            ll x=f(j,0);
            if(x==-1)res[0].pb(-1);
            else if(x==-2)res[0].pb(-2);
            else res[0].pb(m+x);
        }
        m+=tmp[0];
    }
    REP(i,1,tmp.size()){
        vector<vector<int>> v(tmp[i-1]);
        rep(k,tmp[i-1])v[k].pb(i%2);
        rep(k,tmp[i-1])rep(j,N){
            ll x=f(j,i-1);
            if(x==-1)v[k].pb(-1-i%2);
            else if(x==-2)v[k].pb(-2+i%2);
            else if(k<x)v[k].pb(-2+i%2);
            else if(k>x)v[k].pb(-1-i%2);
            if(k==x){
                ll y=f(j,i);
                if(y==-1)v[k].pb(-1-i%2);
                else if(y==-2)v[k].pb(-2+i%2);
                else v[k].pb(m+y);
            }
        }
        rep(k,tmp[i-1])res.pb(v[k]);
        m+=tmp[i];
    }
    return res;
}

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