oj.uz

Submission #769457

# Submission time Handle Problem Language Result Execution time Memory
769457 2023-06-29T15:26:35 Z mousebeaver Prisoner Challenge (IOI22_prison) C++17
100 / 100
 10 ms 1000 KB 
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<std::vector<int>> devise_strategy(int N)
{
    int n = 5000;
    vector<int> range = {5000, 1666, 555, 185, 61, 20, 6, 2}; //Sizes of the blocks (7 elements)
    vector<vector<int>> output(21, vector<int> (n+1));

    for(int i = 0; i <= 20; i++)
    {
        int bit = (i+2)/3;
        output[i][0] = bit%2;
        int indval = (i == 0) ? 0 : (i-1)%3; //Val of bit according to index i

        for(int j = 1; j <= n; j++)
        {
            int k = j; //Value in range from 1 to range[bit]
            int val = 0; //Value of the previous bit
            for(int a = 0; a < bit; a++)
            {
                k--; //We can exclude the smallest value
                if(k <= 0)
                {
                    break;
                }
                val = (k-1)/range[a+1];
                k = 1+(k-1)%range[a+1]; //Break down to the new range
            }

            if(k <= 0)
            {
                output[i][j] = -1-(bit%2);
                continue;
            }

            if(val < indval || (val == indval && k == 1))
            {
                //Current bag is smaller
                output[i][j] = -1-(bit%2);
            }
            else if(val > indval || (val == indval && k == range[bit]))
            {
                //Other bag is smaller
                output[i][j] = -2+(bit%2);
            }
            else
            {
                //Answer lies in the next block!
                k--;
                int nval = (k-1)/range[bit+1]; //Value of the next bit
                output[i][j] = 3*bit + 1 + nval;
            }
        }
    }

    for(int i = 0; i <= 20; i++)
    {
        while((int) output[i].size() > N+1)
        {
            output[i].pop_back();
        }
    }

    return output;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 664 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 6 ms 820 KB Output is correct
5 Correct 9 ms 976 KB Output is correct
6 Correct 10 ms 980 KB Output is correct
7 Correct 10 ms 1000 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 6 ms 724 KB Output is correct
12 Correct 9 ms 916 KB Output is correct