Submission #825540

#	Time	Username	Problem	Language	Result	Execution time	Memory
825540		PixelCat	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	5 ms	724 KiB

prison

#include "prison.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

int kth_digit(int x, int b, int k) {
    while(k--) x /= b;
    return x % b;
}

vector<vector<int>> devise_strategy(int N) {
    int x = 8 * 3 + 1;
    vector<vector<int>> res(x);
    res[0].eb(0);
    For(i, 1, N) res[0].eb(kth_digit(i, 3, 7) + 1);
    For(i, 1, x - 1) {
        int k = 7 - ((i - 1) / 3);
        int dig = (i - 1) % 3;
        if(k % 2) res[i].eb(0);
        else res[i].eb(1);
        For(num, 1, N) {
            int dig2 = kth_digit(num, 3, k);
            if(dig2 > dig) {
                if(k % 2) res[i].eb(-2);
                else res[i].eb(-1);
            } else if(dig2 < dig) {
                if(k % 2) res[i].eb(-1);
                else res[i].eb(-2);
            } else if(k == 0) {
                res[i].eb(0);
            } else {
                res[i].eb(i - dig + 3 + kth_digit(num, 3, k - 1));
            }
        }
    }
    return res;
}

/*

3
1 2
1 3
2 1
2 3
3 1
3 2
-1

A
A
B
A
B
B

*/

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