Submission #1246768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246768		NekoRolly	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	7 ms	1360 KiB

prison

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

vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> vans;

    int bits[n+1][8];

    for (int cnt=1; cnt<=n; cnt++){
        int x = cnt;
        for (int i=0; i<8; i++){
            bits[cnt][i] = x%3;
            x /= 3;
        }
    }

    int found[] = {-1, -2};

    vector<int> aux = {0};
    for (int val=1; val<=n; val++)
        aux.push_back(1+bits[val][7]); // 1 2 3
    vans.push_back(aux);

    for (int est=1; est<=21; est++){
        int id = 7 - (est-1)/3;
        int bolsa = id%2 == 1 ? 0 : 1; // 0 es A, 1 es B
        int bit = (est-1)%3;
        
        aux = {1-bolsa};

        for (int val=1; val<=n; val++){
            if (bits[val][id] < bit)
                aux.push_back(found[1-bolsa]);
            else if (bits[val][id] > bit)
                aux.push_back(found[bolsa]);
            else if (est <= 18)
                aux.push_back(3*(8-id) + bits[val][id-1] + 1);
            else if (bits[val][id-1] == 1)
                aux.push_back(22);
            else if (bits[val][id-1] == 2)
                aux.push_back(found[bolsa]);
            else
                aux.push_back(found[1-bolsa]);
        }
        
        vans.push_back(aux);
    }
    // 7 6 5 4 3 2 1 0
    // A B A B A B A B
    // estado 22 : bit 0 de B es 1
    aux = {0};
    for (int val=1; val<=n; val++){
        if (bits[val][0] == 0)
            aux.push_back(-1);
        else
            aux.push_back(-2);
    }

    vans.push_back(aux);
/*
    for (vector<int> &vec : vans){
        for (int x : vec)
            cout << x << " ";
        cout << "\n";
    }
*/
    return vans;
}

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