제출 #1092358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092358		ainta	죄수들의 도전 (IOI22_prison)	C++17	100 / 100	7 ms	1116 KiB

prison

#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#include "prison.h"

int Nxt[21]={
    18,
    0,
    0,
    1,
    1,
    1,
    3,
    3,
    3,
    6,
    6,
    6,
    9,
    9,
    9,
    12,
    12,
    12,
    15,
    15,
    15
};
void Go(int i, int b, int e, int b2, int e2, vc<vi> &w){
    if(i==18 || i==19 || i==20)w[i][0]=1;
    if(i==12 || i==13 || i==14)w[i][0]=1;
    if(i==6 || i==7 || i==8)w[i][0]=1;
    if(i==1 || i==2)w[i][0]=1;

    rng(j,b2,b)w[i][j]= -w[i][0] - 1;
    rng(j,e,e2)w[i][j]= -(!w[i][0]) - 1;
    if(e-b<=1)return;
    int ob=b,oe=e;
    b++,e--;
    if(b>e)return;

    int p1 = (b*2+e)/3;
    int p2 = (b+e*2)/3;
    if(i==0 || i>=6){
        rng(j,b, p1){
            w[i][j] = Nxt[i];
        }
        rng(j,p1+1, p2){
            w[i][j] = Nxt[i]+1;
        }
        rng(j,p2+1, e){
            w[i][j] = Nxt[i]+2;
        }
        Go(Nxt[i],b,p1,ob,oe,w);
        Go(Nxt[i]+1,p1+1,p2,ob,oe,w);
        Go(Nxt[i]+2,p2+1,e,ob,oe,w);
    }
    else if(i>=3){
        int mid = (b+e)>>1;
        rng(j,b,e){
            if(j<=mid) w[i][j]=1;
            else w[i][j]=2;
        }
        Go(1,b,mid,ob,oe,w);
        Go(2,mid+1,e,ob,oe,w);
    }
    else{
        while(1){}
    }
}

std::vector<std::vector<int>> devise_strategy(int N) {
    vc<vi>w(21,vi(N+1));
    Go(0, 1, N, 1, N, w);
    return w;
}

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