Submission #961362

#	Time	Username	Problem	Language	Result	Execution time	Memory
961362		Boomyday	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1572 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;

int MAXN = 5000;

vector<vector<int>> ans(21,vector<int>(MAXN + 1, 0));
vector<int> seps = {3,3,3,3,3,2,2,1};
vector<int> prefs = {0,3,6,9,12,15,17,19,20};


void upd(int left, int right, int cur,int lev,int bag){
    //cout << "l " << left << " r " << right << " lev " << lev << " cur " << cur << endl;
    ans[cur][0] = bag;
    ans[cur][left] = (bag==0)?-1:-2;
    ans[cur][right] = (bag==0)?-2:-1;


    int newleft = left+1, newright = right-1;
    if (newleft > newright) return;
    int div = (newright-newleft+1)/seps[lev];
    //cout << "nl " << newleft << " nr " << newright << " lev " << lev << endl;
    //cout <<"div " << div << endl;

    for(int i=0;i<seps[lev];++i){
        int ll = newleft + i*div;
        int rr = ((i==seps[lev]-1)?newright:newleft+(i+1)*div - 1);
        for(int j=ll;j<=rr;++j){
            ans[cur][j] = prefs[lev]+i+1;
        }
        for(int j = left; j<ll;++j){
            ans[prefs[lev]+i+1][j] = (bag==0)?-2:-1;
        }
        for(int j=rr+1;j<=right;++j){
            ans[prefs[lev]+i+1][j] = (bag==0)?-1:-2;
        }
        upd(ll,rr ,prefs[lev]+i+1,lev+1,1-bag);
    }

}
vector<vector<int>> devise_strategy(int N) {
    upd(1,5000,0,0,0);
    // print out the first row of the array

    for(auto&i:ans){
        i.resize(N+1);
    }

    return ans;
}


/*
#include <cassert>
#include <cstdio>

#include <string>
#include <vector>

static constexpr int kNumPrisoners = 500;

static void invalid_strategy(std::string message) {
    printf("%s\n", message.c_str());
    exit(0);
}

int main() {
    int N;
    assert(1 == scanf("%d", &N));

    std::vector<std::vector<int>> strategy = devise_strategy(N);
    if (strategy.size() == 0) {
        invalid_strategy("s is an empty array");
    }
    int x = strategy.size() - 1;
    for (int i = 0; i <= x; ++i) {
        if (static_cast<int>(strategy[i].size()) != N + 1) {
            invalid_strategy("s[i] contains incorrect length");
        }
        if (strategy[i][0] < 0 || strategy[i][0] > 1) {
            invalid_strategy("First element of s[i] is non-binary");
        }
        for (int j = 1; j <= N; ++j) {
            if (strategy[i][j] < -2 || strategy[i][j] > x) {
                invalid_strategy("s[i][j] contains incorrect value");
            }
        }
    }

    FILE *log_file = fopen("log.txt","w");

    int A, B;
    while (1 == scanf("%d", &A) && A != -1) {
        assert(1 == scanf("%d", &B));
        bool answer = false;
        int whiteboard = 0;
        for (int i = 0; i < kNumPrisoners && !answer; ++i) {
            int check = strategy[whiteboard][0];
            whiteboard = strategy[whiteboard][check == 0 ? A : B];
            if (whiteboard < 0) {
                answer = true;
                printf("%c\n", "BA"[whiteboard + 2]);
            } else {
                if (i > 0) {
                    fprintf(log_file, " ");
                }
                fprintf(log_file, "%d", whiteboard);
            }
        }
        if (!answer) {
            printf("X\n");
        }
        fprintf(log_file, "\n");
        fflush(log_file);
    }
}
*/

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