Submission #1026449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026449		Mardonbekhazratov	Prisoner Challenge (IOI22_prison)	C++17	5 / 100	9 ms	20432 KiB

prison

#include "prison.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int>a;
vector<vector<int>>ans;

void solve(int l,int r,int c,int id){
    ans[id][0]=c;
    c^=1;
    for(int i=1;i<l;i++){
        ans[id][i]=c^(-2);
    }
    for(int i=r+1;i<=n;i++){
        ans[id][i]=c^(-1);
    }
    ans[id][l]=c^(-2);
    ans[id][r]=c^(-1);
    if(l>=r-1) return;
    l++,r--;
    int mid=(l+r)/2;
    ans.push_back(vector<int>(n+1));
    for(int i=l;i<=mid;i++) ans[id][i]=ans.size()-1;
    solve(l,mid,c,ans.size()-1);
    if(mid>=r) return;
    ans.push_back(vector<int>(n+1));
    for(int i=mid+1;i<=r;i++) ans[id][i]=ans.size()-1;
    solve(mid+1,r,c,ans.size()-1);
}

std::vector<std::vector<int>> devise_strategy(int N) {
    n=N;
    ans.assign(1,vector<int>(N+1));
    solve(1,N,0,0);
    // cout<<ans.size()<<'\n';
    // for(auto x:ans){
    //     for(auto y:x) cout<<y<<' ';
    //     cout<<'\n';
    // }
    return ans;
}

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