Submission #858687

#	Time	Username	Problem	Language	Result	Execution time	Memory
858687		12345678	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	12 ms	1884 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

const int nx=6561, kx=24;
int p[11];
vector<vector<int>> ans(kx+1, vector<int> (nx+1));

std::vector<std::vector<int>> devise_strategy(int N) {
    for (int i=1; i<=nx; i++) ans[0][i]=(i-1)/2187+1;
    p[0]=1;
    for (int i=1; i<11; i++) p[i]=p[i-1]*3;
    for (int i=1; i<=kx; i++)
    {
        int col=(i-1)/3+1, pw=p[8-col], pv=(i-1)%3;
        bool isa=col%2;
        ans[i][0]=(int)isa;
        
        for (int j=1; j<=nx; j++)
        {
            int rem=((j-1)%p[8-col+1])/pw;
            if (rem!=pv)
            {
                if ((rem>pv&&isa)||(rem<pv&&!isa)) ans[i][j]=-1;
                if ((rem>pv&&!isa)||(rem<pv&&isa)) ans[i][j]=-2;
            }
            else
            {
                if (3*col==kx) continue;
                int np=p[8-col-1], nw=(j-1)%p[8-col];
                ans[i][j]=nw/np+1+3*col;
            }
        }
        //cout<<i<<' '<<col<<' '<<isa<<' '<<pw<<' '<<pv<<'\n';
    }
    vector<vector<int>> ans2(kx+1, vector<int> (N+1));
    for (int i=0; i<=kx; i++) for (int j=0; j<=N; j++) ans2[i][j]=ans[i][j];
    return ans2;
}

/*
5000
2 2324
3223 1241
342 5434
9 23
1 2
2 1
234 3242
-1
*/

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