Submission #975798

#	Time	Username	Problem	Language	Result	Execution time	Memory
975798		ALeonidou	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	10 ms	1392 KiB

prison

#include "prison.h"

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

#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define endl "\n"
#define pb push_back

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for(ll i =0; i<sz(v); i++){
    cout<<v[i]<<" ";
    }
    cout<<endl;
}

void printVct2D(vector <vi> v){
    for (ll i =0; i<sz(v); i++){
        cout<<i<<": ";
        for(ll j =0;j<sz(v[i]); j++){
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
}

ll getAns(ll bag_that_is_less){
    if (bag_that_is_less == 0) return -1;
    return -2;
}

vector<vi> devise_strategy(int n) {
    //STEP 1: pre-calculate the 3-base representation of all numbers from 0 to 5000
    ll p3[8];
    p3[0] = 1;
    for (ll i =1; i<=7; i++){
        p3[i] = p3[i-1] * 3;
    }
    vector < vi > b3(5001, vi(8,0));
    for (ll i =1; i<=5000; i++){
        ll num = i;
        for (ll pos = 7; pos >= 0; pos--){
            b3[i][pos] = num / p3[pos];
            num -= b3[i][pos] * p3[pos];
        }
    }
    // cout<<"1: "; printVct(b3[1]);
    // cout<<"3: "; printVct(b3[3]);
    // cout<<"4: "; printVct(b3[4]);

    vector <vi> s(23, vi(n+1));

    //STEP 2: Construct first row
    ll firstRow = 1;
    s[0][0] = 0;
    s[0][1] = -1;
    s[0][n] = -2;
    for (ll i =1; i<=n; i++){
        ll d = b3[i][7];
        // dbg2(i,d);
        if (d == 0) s[0][i] = firstRow;
        else if (d == 1) s[0][i] = firstRow+1;
        else if (d == 2) s[0][i] = firstRow+2;
    }
    // printVct2D(s);

    //STEP 3: Construct first 7 full row
    ll curBag = 1;      //0=A, 1=B
    for (ll curDigit = 7; curDigit>0; curDigit--){
        firstRow += 3;
        for (ll row = 0; row<3; row++){   //loop throug all rows current digit
            ll rowIdx = (7-curDigit) * 3 + row + 1;
            s[rowIdx][0] = curBag;
            for (ll i = 1; i<=n; i++){
                ll d = b3[i][curDigit];
                if (d < row) s[rowIdx][i] = getAns(curBag);
                else if (d > row) s[rowIdx][i] = getAns(!curBag);
                else{
                    ll d2 = b3[i][curDigit-1];
                    if (curDigit != 1){
                        if (d2 == 0) s[rowIdx][i] = firstRow;
                        else if (d2 == 1) s[rowIdx][i] = firstRow+1;
                        else if (d2 == 2) s[rowIdx][i] = firstRow+2;                        
                    }
                    else{   //second last row
                        if (d2 == 0) s[rowIdx][i] = getAns(curBag);
                        else if (d2 == 1) s[rowIdx][i] = firstRow;
                        else if (d2 == 2) s[rowIdx][i] = getAns(!curBag);          
                    }
                }
            }
        }
        curBag = !curBag;
    }

    //STEP 4: Construct last row
    const int lastRow = 22;
    curBag = 0;
    s[lastRow][0] = curBag;
    for (ll i =1; i<=n; i++){
        ll d = b3[i][0];
        if (d == 0) s[lastRow][i] = getAns(curBag);
        else if (d == 2) s[lastRow][i] = getAns(!curBag);
        //d = 1 is not possible
    }

    // printVct2D(s);

    return s;
}

/*
5
3 4
-1

2
1 2
-1

5000
3 4
2 5
4 1
245 234
12 2304
4019 4000
-1

*/

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