Submission #626146

#	Time	Username	Problem	Language	Result	Execution time	Memory
626146		peti1234	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1364 KiB

prison

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > devise_strategy(int n){
    vector<vector<int>> ans(21), ert(9), spec(9);
    vector<int> szint(21, 0);
    for (int i=0; i<=20; i++) {
        ans[i].resize(n+1);
        if (i<=8) ert[i].resize(n+1), spec[i].resize(n+1);
    }
    for (int i=0; i<=19; i++) {
        szint[i]=(i+2)/3;
    }
    szint[20]=8;
    for (int i=0; i<=20; i++) {
        ans[i][0]=(szint[i]%2);
    }
    for (int j=1; j<=n; j++) {
        int kis=1, nagy=5102;
        for (int i=0; i<=8; i++) {
            int res=0, res2=0;
            if (j==kis) res2=-1, res=1;
            if (j==nagy) res2=-2, res=3;
            if (kis<j && j<nagy) {
                kis++, nagy--;
                if (i<6) {
                    int k1=kis+(nagy+1-kis)/3, k2=2*k1-kis;
                    if (j<k1) res=1, nagy=k1-1;
                    else if (j<k2) res=2, kis=k1, nagy=k2-1;
                    else res=3, kis=k2;
                }
                if (i==6) res=19;
                if (i==7) res=20;
                if (i==8) res=0;
            }
            ert[i][j]=res, spec[i][j]=res2;
        }
    }
    for (int i=0; i<=20; i++) {
        for (int j=1; j<=n; j++) {
            int ut=(1<=i && i<=18 ? (i-1)%3+1 : 0), b=ert[szint[i]][j], sp=spec[szint[i]][j], el=(1<=i && i<=18 ? ert[szint[i]-1][j] : 0);
            if (ut!=el || sp) {
                if (ut!=el) ans[i][j]=(el<ut ? -1 : -2);
                else ans[i][j]=sp;
                if (szint[i]%2) ans[i][j]=-3-ans[i][j];
            } else {
                ans[i][j]=(i<16 ? i+(3-i%3)%3+b : b);
            }
        }
    }
    return ans;
}

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