oj.uz

Submission #627250

# Submission time Handle Problem Language Result Execution time Memory
627250 2022-08-12T11:40:48 Z phathnv Prisoner Challenge (IOI22_prison) C++17
100 / 100
 10 ms 980 KB 
#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

void gen(int ord, int num, int l, int r, vector<vector<int>> &strat, const vector<int>& a) {
    if (ord == (int) a.size()) {
        assert(l + 1 == r);
        strat[num][0] = ord % 2;
        strat[num][l] = (ord % 2 == 0? -1 : -2);
        strat[num][r] = (ord % 2 == 0? -2 : -1);
        return;
    }

    int offset = 1;
    for (int i = 0; i < ord; ++i) {
        offset += a[i];
    }
    strat[num][0] = ord % 2;
    strat[num][l] = (ord % 2 == 0? -1 : -2);
    strat[num][r] = (ord % 2 == 0? -2 : -1);
    for (int i = 0; i < a[ord]; ++i) {
        strat[offset + i][l] = (ord % 2 == 0? -2 : -1);
        strat[offset + i][r] = (ord % 2 == 0? -1 : -2);
    }
    ++l, --r;

    int len = (r - l + 1) / a[ord];
    for (int i = 0; i < a[ord]; ++i) {
        for (int x = l + len * i; x <= l + len * (i + 1) - 1; ++x) {
            strat[num][x] = offset + i;
        }

        for (int j = 0; j < a[ord]; ++j) {
            if (i == j) {
                gen(ord + 1, offset + i, l + len * i, l + len * (i + 1) - 1, strat, a);
            } else if (j < i) {
                for (int x = l + len * j; x <= l + len * (j + 1) - 1; ++x) {
                    strat[offset + i][x] = (ord % 2 == 0? -2 : -1);
                }
            } else {
                for (int x = l + len * j; x <= l + len * (j + 1) - 1; ++x) {
                    strat[offset + i][x] = (ord % 2 == 0? -1 : -2);
                }
            }
        }
    }

}

vector<vector<int>> genStrat(vector<int> a) {
    int x = accumulate(a.begin(), a.end(), 0);
    int n = 2;
    for (int i = a.size() - 1; i >= 0; --i) {
        n = n * a[i] + 2;
    }

    vector<vector<int>> strat(x + 1, vector<int>(n + 1, 0));
    gen(0, 0, 1, n, strat, a);

    return strat;
}

vector<vector<int>> devise_strategy(int N) {
    vector<vector<int>> res = genStrat({3, 3, 3, 3, 2, 2, 2, 2});
    for (auto &v : res) {
        v.resize(N + 1);
    }
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 684 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 684 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 636 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 9 ms 928 KB Output is correct
6 Correct 10 ms 980 KB Output is correct
7 Correct 10 ms 980 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 664 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 5 ms 852 KB Output is correct
12 Correct 8 ms 936 KB Output is correct