Submission #626814

#	Time	Username	Problem	Language	Result	Execution time	Memory
626814		typ_ik	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	13 ms	1644 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " : " << x << '\n'

using namespace std;

const int N = 5e3 + 5;
vector <int> notation[N];

bool inited = false;

vector <int> step3(int x) {
    vector <int> cur;

    for (int i = 0; i < 8; i++)
        cur.push_back(x % 3), x /= 3;

    return vector<int>(cur.rbegin(), cur.rend());
}

void init() {
    if (inited)
        return;
    inited = true;

    for (int i = 0; i < N; i++)
        notation[i] = step3(i);
}

vector<vector<int>> devise_strategy(int N) {
    init();

    vector < vector<int> > ans;

    ans.push_back({0});
    for (int i = 0; i < N; i++)
        ans.back().push_back(1+notation[i][0]);

    for (int p = 0; p < 8; p++) {
        for (int x = 0; x < 3; x++) {
            int isB = p & 1 ^ 1, isA = p & 1;

            ans.push_back({isB});

            for (int i = 0; i < N; i++)
                if (notation[i][p] != x) {
                    if (notation[i][p] > x) ans.back().push_back(-1 + -isA);
                        else ans.back().push_back(-1 + -isB);
                } else if (p + 1 < 8) {
                    ans.back().push_back(1+notation[i][p + 1] + 3 * (p + 1));
                } else {
                    ans.back().push_back(-1 + -isB);
                }
        }
    }

    return ans;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:45:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   45 |             int isB = p & 1 ^ 1, isA = p & 1;
      |                       ~~^~~

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