Submission #1248804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248804		DeathIsAwe	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	14 ms	1348 KiB

prison

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long


int base3(int a, int pos) {
    for (int i=0;i<pos-1;i++) {
        a /= 3;
    }
    return a % 3;
}


vector<vector<int>> devise_strategy(int n) {
    vector<vector<int>> ansvec(23);
    ansvec[0].pb(0);
    for (int i=1;i<23;i++) {
        if (((i - 1) / 3) % 2 == 0) {
            ansvec[i].pb(1);
        } else {
            ansvec[i].pb(0);
        }
    }
    for (int i=1;i<n+1;i++) {
        ansvec[0].pb(base3(i, 8) + 1);
    }


    int temp1, temp2;
    for (int i=1;i<8;i++) {
        for (int j=1;j<n+1;j++) {
            temp1 = base3(j, 9 - i);
            temp2 = 3 * i + base3(j, 8 - i) + 1;
            //if (i == 7) {
            //    cout << temp1 << ' ' << temp2 << '\n';
            //}
            for (int k=0;k<3;k++) {
                if (temp1 > k) {
                    if (i % 2 == 0) ansvec[3 * i - (2 - k)].pb(-2);
                    else ansvec[3 * i - (2 - k)].pb(-1);
                } else if (temp1 < k) {
                    if (i % 2 == 0) ansvec[3 * i - (2 - k)].pb(-1);
                    else ansvec[3 * i - (2 - k)].pb(-2);
                } else {
                    if (i == 7) {
                        if (j % 3 == 0) {
                            ansvec[3 * i - (2 - k)].pb(-2);
                        } else if (j % 3 == 2) {
                            ansvec[3 * i - (2 - k)].pb(-1);
                        } else {
                            ansvec[3 * i - (2 - k)].pb(22);
                        }
                    } else {
                        ansvec[3 * i - (2 - k)].pb(temp2);
                    }
                }
            }
        }
    }
    for (int i=1;i<n+1;i++) {
        if (i % 3 == 0) {
            ansvec[22].pb(-1);
        } else if (i % 3 == 2) {
            ansvec[22].pb(-2);
        } else {
            ansvec[22].pb(0);
        }
    }


    return ansvec;
}

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