Submission #1158794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158794		Bolatulu	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	6 ms	1092 KiB

prison

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

#pragma GCC optimize("Ofast")   
#pragma GCC target("avx,avx2,fma")  
#pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("inline")

#define pb push_back
#define eb emplace_back
#define md ((tl + tr) >> 1)
#define TL v + v, tl, md
#define TR v + v + 1, md + 1, tr
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;
const ll INF = 1e18 + 7;  

vector <vector <int>> devise_strategy(int n) {
    if (n == 2) {
        vector <vector <int>> res(1, vector <int> (n + 1));
        res[0][0] = 0;
        res[0][1] = -1;
        res[0][2] = -2;
        return res;
    }
    int lg = 0, z = 1;
    while (z <= n) {
        lg++;
        z *= 3;
    }
    lg--;
    z /= 3;
    vector <vector <int>> res(lg * 3 + 2, vector <int> (n + 1));
    res[0][0] = !(lg & 1);
    for (int i = 1;i <= n;i++) {
        res[0][i] = i / z % 3 + 1;
    }
    int cur = 1;
    for (int i = lg;i >= 1;i--) {
        res[cur][0] = res[cur + 1][0] = res[cur + 2][0] = i & 1;
        for (int j = 1;j <= n;j++) {
            int bit = j / z % 3, bit1 = j / (z / 3) % 3;
            res[cur][j] = res[cur + 1][j] = res[cur + 2][j] = cur + 3 + bit1;
            if (i == 1)
                res[cur][j] = res[cur + 1][j] = res[cur + 2][j] = cur + 3;
            if (bit == 0) {
                res[cur + 1][j] = -1 - (i & 1);
                res[cur + 2][j] = -1 - (i & 1); 
            } else if (bit == 1) {
                res[cur][j] = -1 - !(i & 1);
                res[cur + 2][j] = -1 - (i & 1);
            } else {
                res[cur][j] = -1 - !(i & 1);
                res[cur + 1][j] = -1 - !(i & 1);
            }
            if (i == 1) {
                if (bit1 == 0) {
                    if (res[cur][j] > 0)
                        res[cur][j] = -1 - (i & 1);
                    if (res[cur + 1][j] > 0)
                        res[cur + 1][j] = -1 - (i & 1);
                    if (res[cur + 2][j] > 0)
                        res[cur + 2][j] = -1 - (i & 1);
                } else if (bit1 == 2) {
                    if (res[cur][j] > 0)
                        res[cur][j] = -1 - !(i & 1);
                    if (res[cur + 1][j] > 0)
                        res[cur + 1][j] = -1 - !(i & 1);
                    if (res[cur + 2][j] > 0)
                        res[cur + 2][j] = -1 - !(i & 1);
                }
            }
        }
        cur += 3;
        z /= 3;
    }
    for (int i = 1;i <= n;i++) {
        if (i % 3 == 0)
            res[cur][i] = -1;
        else
            res[cur][i] = -2;
    }
    return res;
}

// void solve() {
//     int n, m;
//     cin >> n >> m;
//     vector <int> x(m), y(m), w(m);
//     for (int i = 0;i < m;i++)
//         cin >> x[i] >> y[i] >> w[i];
//     cout << max_weights(n, m, x, y, w);
// }

// signed main() {
//     solve();
//     return 0;
// }        

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