Submission #667071

#	Time	Username	Problem	Language	Result	Execution time	Memory
667071		tatyam	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	980 KiB

prison

#include <bits/stdc++.h>
using namespace std;


vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> A(21, vector<int>(N + 1));
    vector<vector<int>> idx = {
        {0},
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
        {10, 11, 12},
        {13, 14, 15},
        {16, 17, 18},
        {19, 20}
    };
    for(int k = 0; k < idx.size(); k++) for(int i : idx[k]) A[i][0] = k % 2;
    auto f = [&](int k, int i, int L, int R, auto f){
        if(R - L <= 1) return;
        A[i][L] = k % 2 ? -2 : -1;
        A[i][R - 1] = k % 2 ? -1 : -2;
        if(R - L == 2) return;
        for(int i : idx[k + 1]) {
            A[i][L] = k % 2 ? -1 : -2;
            A[i][R - 1] = k % 2 ? -2 : -1;
        }
        L++; R--;
        const int W = R - L, D = idx[k + 1].size();
        vector<int> block;
        for(int b = 0; b <= D; b++) block.push_back(L + W * b / D);
        for(int b = 0; b < D; b++){
            const int l = block[b], r = block[b + 1];
            for(int x = l; x < r; x++) A[i][x] = idx[k + 1][b];
        }
        for(int b = 0; b < D; b++) for(int b2 = 0; b2 < D; b2++) if(b != b2){
            const int l = block[b2], r = block[b2 + 1];
            for(int x = l; x < r; x++) A[idx[k + 1][b]][x] = b < b2 ^ k % 2 ? -1 : -2;
        }
        for(int b = 0; b < D; b++) f(k + 1, idx[k + 1][b], block[b], block[b + 1], f);
    };
    f(0, 0, 1, N + 1, f);
    return A;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int k = 0; k < idx.size(); k++) for(int i : idx[k]) A[i][0] = k % 2;
      |                    ~~^~~~~~~~~~~~
prison.cpp: In instantiation of 'devise_strategy(int)::<lambda(int, int, int, int, auto:23)> [with auto:23 = devise_strategy(int)::<lambda(int, int, int, int, auto:23)>]':
prison.cpp:41:24:   required from here
prison.cpp:37:64: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   37 |             for(int x = l; x < r; x++) A[idx[k + 1][b]][x] = b < b2 ^ k % 2 ? -1 : -2;
      |                                                              ~~^~~~

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