Submission #638006

#	Time	Username	Problem	Language	Result	Execution time	Memory
638006		huutuan	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	2 ms	724 KiB

prison

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

using namespace std;

#define sz(a) ((int)a.size())

vector<int> base={3, 3, 3, 3, 3, 2, 2, 1};
vector<vector<int>> v;
vector<vector<int>> states={{0}, {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}, {13, 14, 15}, {16, 17}, {18, 19}, {20}};
int n;

vector<int> divide(int depth, int l, int r){
    int t=base[depth];
    if (t==1) return {r};
    if (t==2) return {(l+r)/2, r};
    if (t==3) return {l+(r-l)/3, l+(r-l)/3*3, r};
}

void dnc(int depth, int l, int r, bool box){
    if (l>r) return;
    if (l==r){
        v[states[depth][0]][0]=box;
        for (int j=1; j<=n; ++j) if (j<l) v[states[depth][0]][j]=-1-box; else v[states[depth][0]][j]=-2+box;
        return;
    }
    auto vv=divide(depth, l+1, r-1);
    while (sz(vv)>1 && vv.back()<=vv[sz(vv)-2]) vv.pop_back();
    for (int i=0; i<sz(states[depth]); ++i){
        v[states[depth][i]][0]=box;
        int id=0;
        for (int j=1; j<=n; ++j){
            if (j<=l) v[states[depth][i]][j]=-1-box;
            else if (j>=r) v[states[depth][i]][j]=-2+box;
            else{
                if (j>vv[id]) ++id;
                if (i<id) v[states[depth][i]][j]=-1-box;
                else if (i>id) v[states[depth][i]][j]=-2+box;
                else{
                    auto vvv=divide(depth+1, i?vv[i-1]:l+1, vv[i]);
                    while (sz(vvv)>1 && vvv.back()<=vvv[sz(vvv)-2]) vvv.pop_back();
                    int t=upper_bound(vvv.begin(), vvv.end(), j)-vvv.begin()-1;
                    v[states[depth][i]][j]=states[depth+1][t];
                }
            }
        }
    }
    for (int i=0; i<sz(vv); ++i) dnc(depth+1, i?vv[i-1]:l+1, vv[i], box^1);
}

vector<vector<int>> devise_strategy(int N){
    n=N;
    vector<vector<int>>(21, vector<int>(n+1)).swap(v);
    dnc(0, 1, n, 0);
    return v;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<int> divide(int, int, int)':
prison.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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