Submission #685404

#	Time	Username	Problem	Language	Result	Execution time	Memory
685404		79brue	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	980 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

int grp[] = {0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7};
int off[] = {0, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2};
int seq[] = {3, 3, 3, 3, 3, 3, 2};
int lim[] = {5102, 1700, 566, 188, 62, 20, 6, 2, 1};
int stt[] = {0, 1, 4, 7, 10, 13, 16, 19};

vector<vector<int> > devise_strategy(int N){
    n = N;
    vector<vector<int> > ret (21);
    for(int c=0; c<=20; c++){
        ret[c].resize(N+1);
        int g = grp[c];
        ret[c][0] = g%2;
        for(int i=1; i<=N; i++){
            if(i == 1702){
                printf("");
            }
            int v = i;
            bool bad = 0;
            for(int j=0; j<g; j++){
                if(v == 1 || v == lim[j]){
                    if(v == 1) ret[c][i] = (g%2) ? -2 : -1, bad = 1;
                    else       ret[c][i] = (g%2) ? -1 : -2, bad = 1;
                    break;
                }
                if(j == g-1 && (v-2)/lim[j+1]+1 != off[c]){
                    if((v-2)/lim[j+1]+1 < off[c]) ret[c][i] = (g%2) ? -2 : -1, bad = 1;
                    else                          ret[c][i] = (g%2) ? -1 : -2, bad = 1;
                    break;
                }
                v = (v - 2) % lim[j+1] + 1;
            }
            if(bad) continue;
            /// 가능한 답안인 경우
            if(v == 1) ret[c][i] = (g%2) ? -2 : -1;
            else if(v == lim[g]) ret[c][i] = (g%2) ? -1 : -2;
            else if(g==7) ret[c][i] = 0; /// 있을 수 없는 경우
            else if(g==0) ret[c][i] = (v-2)/lim[g+1]+1;
            else{ /// 끝점 아님
                int tv = (v-2)/lim[g]+1;
                if(!g) ret[c][i] = tv;
                else ret[c][i] = stt[g+1] + (v-2)/lim[g+1];
            }
        }
    }
    return ret;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:25:24: warning: zero-length gnu_printf format string [-Wformat-zero-length]
   25 |                 printf("");
      |                        ^~

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