제출 #1157513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157513		Math4Life2020	죄수들의 도전 (IOI22_prison)	C++20	0 / 100	1 ms	576 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
ll X = 20;

vector<vector<int>> ans; int N;
int itype[9][5103]; //x -> type (1, 2, 3 or -1 (TOP) or -2 (BOTTOM))

void wtype(ll a, ll b, ll d) {
    if (a>=b ||d>=9) {
        return;
    }
    ll len = b-a+1;
    if (len>=188) {
        itype[d][a]=-2;
        itype[d][b]=-1;
        ll nwid = len/3;
        for (ll i=(a+1);i<=(a+3*nwid);i++) {
            itype[d][i]=(i-a-1)/nwid;
        }
        wtype(a+1,a+nwid,d+1);
        wtype(a+nwid+1,a+2*nwid,d+1);
        wtype(a+2*nwid+1,a+3*nwid,d+1);
    } else {
        itype[d][a]=-2;
        itype[d][b]=-1;
        ll nwid = (len-2)/2;
        for (ll i=(a+1);i<=(a+2*nwid);i++) {
            itype[d][i]=(i-a-1)/nwid;
        }
        wtype(a+1,a+nwid,d+1);
        wtype(a+nwid+1,b-1,d+1);
    }
}

void prc(ll v) {
    for (ll i=1;i<=N;i++) {
        ll inp;
        ll ncur;
        ll nxt;
        if (v<=12) {
            inp = (v-1)%3;
            ncur = (v-1)/3;
            nxt = 3*ncur+4;
        } else {
            inp = (v-1)%2;
            ncur = (v-1)/2-2;
            nxt = 2*ncur+7;
        }
        ll rd = itype[ncur][i];
        if (rd<0) {
            if ((ans[v][0]==0)^(rd==-1)) {
                //checking A XOR isMax
                //min if checking A
                ans[v][i]=-1;
            } else {
                ans[v][i]=-2;
            }
        } else {
            if (rd>inp) {
                if (ans[v][0]==0) {
                    //this is higher than other + checking A
                    ans[v][i]=-2;
                } else {
                    ans[v][i]=-1;
                }
            } else if (rd<inp) {
                if (ans[v][0]==0) {
                    //this is lower than other + checking A
                    ans[v][i]=-1;
                } else {
                    ans[v][i]=-2;
                }
            } else {
                //ans[v][i]=itype[ncur+1][i]+nxt;
                if (itype[ncur+1][i]<0) {
                    if ((ans[v][0]==0)^(itype[ncur+1][i]==-1)) {
                        //checking A XOR isMax
                        //min if checking A
                        ans[v][i]=-1;
                    } else {
                        ans[v][i]=-2;
                    }
                } else {
                    ans[v][i]=itype[ncur+1][i]+nxt;
                    assert(ans[v][i]<=20);
                }
            }
        }
    }
}

vector<vector<int>> devise_strategy(int _N) {
    N = _N;
    vector<int> TEMP(N+1,0);
    for (ll i=0;i<=20;i++) {
        ans.push_back(TEMP);
    }
    wtype(1,5102,0); //write type
    ans[0][0]=0;
    ans[0][1]=-1;
    for (ll i=2;i<=N;i++) {
        ans[0][i]=itype[0][i]+1;
    }
    ans[1][0]=1; //wtype 1
    ans[2][0]=1;
    ans[3][0]=1;
    ans[4][0]=0; //2
    ans[5][0]=0;
    ans[6][0]=0;
    ans[7][0]=1; //3
    ans[8][0]=1;
    ans[9][0]=1;
    ans[10][0]=0; //4
    ans[11][0]=0;
    ans[12][0]=0;
    ans[13][0]=1; //5
    ans[14][0]=1;
    ans[15][1]=0; //6
    ans[16][1]=0;
    ans[17][0]=1; //7
    ans[18][0]=1;
    ans[19][1]=0; //8
    ans[20][1]=0;
    for (ll i=1;i<=20;i++) {
        prc(i);
    }
    return ans;
    //output -1 = A is lower
}

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