Submission #1226561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226561		ericl23302	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	8 ms	1144 KiB

prison

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

using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
    // vector<int> powers = {4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
    // vector<vector<int>> res = {{0}};
    // for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(1);
    // for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(2);
    // for (int i = 0; i < powers.size(); ++i) {
    //     for (int j = 0; j < 2; ++j) {
    //         vector<int> cur = {(i + 1) % 2};
    //         int curNext = i * 2 + 3;
    //         int bagRet = -1;
    //         if ((i + 1) % 2) bagRet = -2;

    //         for (int k = 0; k < N; ++k) {
    //             int val = k;
    //             for (int p = 0; p < i; ++p) {
    //                 int power = powers[p];
    //                 if (val >= power) val -= power;
    //             }
    //             int curDiv = powers[i];
    //             if (val < curDiv && j) cur.push_back(bagRet);
    //             else if (val >= curDiv && !j) cur.push_back(-3 - bagRet);
    //             else {
    //                 if (i < powers.size() - 1) {
    //                     if (val >= curDiv) val -= curDiv;
    //                     curDiv = powers[i + 1];
    //                     if (val < curDiv) cur.push_back(curNext);
    //                     else cur.push_back(curNext + 1);
    //                 } else cur.push_back(0);
    //             }
    //         }
    //         res.push_back(cur);
    //     }
    // }

    vector<int> powers = {2187, 729, 243, 81, 27, 9, 3, 1};
    vector<vector<int>> res = {{0}};
    for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(1);
    for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(2);
    for (int i = 0; i < powers[0] && res[0].size() <= N; ++i) res[0].push_back(3);
    for (int i = 0; i < powers.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            vector<int> cur = {(i + 1) % 2};
            int curNext = i * 3 + 4;
            int bagRet = -1;
            if ((i + 1) % 2) bagRet = -2;

            for (int k = 0; k < N; ++k) {
                int val = k;
                for (int p = 0; p < i; ++p) {
                    int power = powers[p];
                    while (val >= power) val -= power;
                }
                int curDiv = powers[i];
                int valDiv = val / curDiv;
                if (valDiv < j) cur.push_back(bagRet);
                else if (valDiv > j) cur.push_back(-3 - bagRet);
                else {
                    if (i < powers.size() - 1) {
                        while (val >= curDiv) val -= curDiv;
                        curDiv = powers[i + 1];
                        valDiv = val / curDiv;
                        cur.push_back(curNext + valDiv);
                    } else cur.push_back(0);
                }
            }
            res.push_back(cur);
        }
    }

    // int cnt = 0;
    // for (auto &i : res) {
    //     cout << cnt++ << ' ';
    //     for (auto &j : i) cout << j << ' ';
    //     cout << endl;
    // }

    return res;
}

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