oj.uz

Submission #961362

# Submission time Handle Problem Language Result Execution time Memory
961362 2024-04-11T22:28:06 Z Boomyday Prisoner Challenge (IOI22_prison) C++17
100 / 100
 10 ms 1572 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 10 ms 1368 KB Output is correct
7 Correct 9 ms 1572 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct