oj.uz

Submission #629033

# Submission time Handle Problem Language Result Execution time Memory
629033 2022-08-14T04:05:14 Z Lam_lai_cuoc_doi Prisoner Challenge (IOI22_prison) C++17
65 / 100
 60 ms 98324 KB 
#include "prison.h"

#include <vector>
#include <algorithm>
using namespace std;

constexpr int N = 5005;

vector<vector<int>> a;
int n, maxbit;
bool ck[N];

#define bit(i, x) (((x) >> (i)) & 1)

void Recursive(int v)
{

    if (ck[v])
        return;

    ck[v] = 1;

    if (v == 0)
    {
        a[v][0] = 0;

        for (int i = 1; i <= n; ++i)
            a[v][i] = maxbit - 1 + (bit(maxbit, i) * maxbit) + 1;

        for (int i = 1; i <= n; ++i)
            if (a[v][i] > 0)
                Recursive(a[v][i]);

        return;
    }

    --v;
    int number, state;

    if (v >= maxbit)
    {
        state = 1;
        number = v - maxbit;
    }
    else
    {
        state = 0;
        number = v;
    }

    ++number;
    ++v;

    if ((number & 1) == (maxbit & 1))
    {
        a[v][0] = 1;

        for (int i = 1; i <= n; ++i)
            if (bit(number, i) < state)
                a[v][i] = -2;
            else if (bit(number, i) > state)
                a[v][i] = -1;
            else
            {
                if (number == 1)
                {
                    if (bit(0, i))
                        a[v][i] = -1;
                    else
                        a[v][i] = -2;
                }
                else
                    a[v][i] = number - 1 + (bit(number - 1, i) * maxbit);
            }
        for (int i = 1; i <= n; ++i)
            if (a[v][i] > 0)
                Recursive(a[v][i]);
    }
    else
    {
        a[v][0] = 0;

        for (int i = 1; i <= n; ++i)
            if (bit(number, i) < state)
                a[v][i] = -1;
            else if (bit(number, i) > state)
                a[v][i] = -2;
            else
            {
                if (number == 1)
                {
                    if (bit(0, i))
                        a[v][i] = -2;
                    else
                        a[v][i] = -1;
                }
                else
                    a[v][i] = number - 1 + (bit(number - 1, i) * maxbit);
            }

        for (int i = 1; i <= n; ++i)
            if (a[v][i] > 0)
                Recursive(a[v][i]);
    }
}

std::vector<std::vector<int>> devise_strategy(int m)
{
    n = m;
    maxbit = __lg(n);
    a.resize(5000, vector<int>(n + 1, 0));
    Recursive(0);

    while (!ck[a.size() - 1])
        a.pop_back();

    return a;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 3 ms 5152 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 8 ms 10196 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 6 ms 7892 KB Output is correct
9 Correct 8 ms 8532 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 5152 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 8 ms 10196 KB Output is correct
6 Correct 8 ms 10196 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 8 ms 9640 KB Output is correct

Subtask #3
55.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 520 KB Output is correct
4 Partially correct 30 ms 43308 KB Output is partially correct
5 Partially correct 49 ms 80572 KB Output is partially correct
6 Partially correct 60 ms 98312 KB Output is partially correct
7 Partially correct 57 ms 98324 KB Output is partially correct
8 Correct 1 ms 932 KB Output is correct
9 Correct 7 ms 7764 KB Output is correct
10 Correct 11 ms 13396 KB Output is correct
11 Correct 26 ms 39864 KB Output is correct
12 Partially correct 46 ms 79360 KB Output is partially correct