Submission #719549

#	Time	Username	Problem	Language	Result	Execution time	Memory
719549		veehj	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	25 ms	1620 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
vector<vector<int>> ans;

string convert_base_3(int n) {
    string s;
    while (n) {
        s += char(n % 3 + '0');
        n /= 3;
    }
    while (s.size() != 8) s += '0';
    reverse(s.begin(), s.end());
    return s;
}

std::vector<std::vector<int>> devise_strategy(int N) {
    int a=0, b=1, A=-2, B=-1;
    swap(A, B);
    ans.pb({a});
    int nw = 4;
    for(int i=0; i<N; i++){
        ans[ans.size()-1].pb(convert_base_3(i+1)[0]-'0'+1);
    }
    for(int i=1; i<7; i++){
        swap(a, b);
        swap(A, B);
        ans.pb({a});
        for(int j=0; j<N; j++){
            if(convert_base_3(j+1)[i-1]=='1' || convert_base_3(j+1)[i-1]=='2') ans[ans.size()-1].pb(B);
            else ans[ans.size()-1].pb(nw+(int)(convert_base_3(j+1)[i]-'0'));
        }
        ans.pb({a});
        for(int j=0; j<N; j++){
            if(convert_base_3(j+1)[i-1]=='0') ans[ans.size()-1].pb(A);
            else if(convert_base_3(j+1)[i-1]=='2') ans[ans.size()-1].pb(B);
            else ans[ans.size()-1].pb(nw+(int)(convert_base_3(j+1)[i]-'0'));
        }
        ans.pb({a});
        for(int j=0; j<N; j++){
            if(convert_base_3(j+1)[i-1]=='0' || convert_base_3(j+1)[i-1]=='1') ans[ans.size()-1].pb(A);
            else ans[ans.size()-1].pb(nw+(int)(convert_base_3(j+1)[i]-'0'));
        }
        nw+=3;
    }
    swap(a, b);
    swap(A, B);
    ans.pb({a});
    for(int j=0; j<N; j++){
        if(convert_base_3(j+1)[6]=='1' || convert_base_3(j+1)[6]=='2') ans[ans.size()-1].pb(B);
        else if(convert_base_3(j+1)[7]=='0') ans[ans.size()-1].pb(A);
        else if(convert_base_3(j+1)[7]=='1') ans[ans.size()-1].pb(nw);
        else if(convert_base_3(j+1)[7]=='2') ans[ans.size()-1].pb(B);
    }
    ans.pb({a});
    for(int j=0; j<N; j++){
        if(convert_base_3(j+1)[6]=='0') ans[ans.size()-1].pb(A);
        else if(convert_base_3(j+1)[6]=='2') ans[ans.size()-1].pb(B);
        else if(convert_base_3(j+1)[7]=='0') ans[ans.size()-1].pb(A);
        else if(convert_base_3(j+1)[7]=='1') ans[ans.size()-1].pb(nw);
        else if(convert_base_3(j+1)[7]=='2') ans[ans.size()-1].pb(B);
    }
    ans.pb({a});
    for(int j=0; j<N; j++){
        if(convert_base_3(j+1)[6]=='0' || convert_base_3(j+1)[6]=='1') ans[ans.size()-1].pb(A);
        else if(convert_base_3(j+1)[7]=='0') ans[ans.size()-1].pb(A);
        else if(convert_base_3(j+1)[7]=='1') ans[ans.size()-1].pb(nw);
        else if(convert_base_3(j+1)[7]=='2') ans[ans.size()-1].pb(B);
    }
    swap(a, b);
    // swap(A, B);
    ans.pb({a});
    for(int j=0; j<N; j++){
        if(convert_base_3(j+1)[7]=='0') ans[ans.size()-1].pb(B);
        else if(convert_base_3(j+1)[7]=='1') ans[ans.size()-1].pb(A);
        else if(convert_base_3(j+1)[7]=='2') ans[ans.size()-1].pb(A);
    }
    return ans;
}

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