oj.uz

Submission #702927

# Submission time Handle Problem Language Result Execution time Memory
702927 2023-02-25T10:20:12 Z boris_mihov Prisoner Challenge (IOI22_prison) C++17
100 / 100
 12 ms 1820 KB 
#include "prison.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 6000 + 10;
const int INF  = 1e9;

std::vector <int> bitwise[MAXN];
std::vector <int> divide = {3, 3, 3, 3, 3, 2, 2, 1};
inline int encode(int bit, int val)
{
    int sum = 1;
    for (int i = 0 ; i < bit ; ++i)
    {
        sum += divide[i];
    }

    return sum + val;
}

void getBitwise(int num, int l, int r, int where)
{
    if (num == l)
    {
        bitwise[num].push_back(-1);
        return;
    }

    if (num == r)
    {
        bitwise[num].push_back(-2);
        return;
    }

    if (divide[where] == 1)
    {
        int len = (r - l - 1) / 1; 
        bitwise[num].push_back(0);
        getBitwise(num, l + 1, l + len, where + 1);
        return;
    }

    if (divide[where] == 2)
    {
        int len = (r - l - 1) / 2; 
        if (num <= l + len)
        {
            bitwise[num].push_back(0);
            getBitwise(num, l + 1, l + len, where + 1);
            return;
        }

        bitwise[num].push_back(1);
        getBitwise(num, l + len + 1, r - 1, where + 1);
        return;
    }

    int len = (r - l - 1) / 3;
    if (num <= l + len)
    {
        bitwise[num].push_back(0);
        getBitwise(num, l + 1, l + len, where + 1);
        return;
    }

    if (num <= l + 2 * len)
    {
        bitwise[num].push_back(1);
        getBitwise(num, l + len + 1, l + 2*len, where + 1);
        return;
    }

    bitwise[num].push_back(2);
    getBitwise(num, l + 2*len + 1, r - 1, where + 1);
}

std::vector <std::vector <int>> s;
std::vector <std::vector <int>> devise_strategy(int n) 
{
    for (int i = 1 ; i <= n ; ++i)
    {
        getBitwise(i, 1, n, 0);
    }

    s.resize(21);
    s[0].resize(n + 1, 0);
    for (int x = 1 ; x <= n ; ++x)
    {
        if (bitwise[x][0] < 0)
        {
            s[0][x] = bitwise[x][0];
            continue;
        }
        
        s[0][x] = encode(0, bitwise[x][0]);
    }

    for (int bit = 0 ; bit < divide.size() ; ++bit)
    {
        for (int val = 0 ; val < divide[bit] ; ++val)
        {
            s[encode(bit, val)].resize(n + 1, 0);
            s[encode(bit, val)][0] = !(bit & 1);
            for (int money = 1 ; money <= n ; ++money)
            {
                if (bitwise[money].size() <= bit)
                {
                    s[encode(bit, val)][money] = -1;
                    continue;
                }

                int currBit = bitwise[money][bit];
                if (currBit == -1)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -1 : -2);
                    continue;
                }

                if (currBit == -2)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -2 : -1);
                    continue;
                }
                
                if (currBit != val)
                {
                    s[encode(bit, val)][money] = ((currBit < val) ^ (bit & 1) ? -2 : -1);
                    continue;
                }

                if (bitwise[money][bit + 1] == -1)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -1 : -2);
                    continue;
                }

                if (bitwise[money][bit + 1] == -2)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -2 : -1);
                    continue;
                }

                if (encode(bit + 1, bitwise[money][bit + 1]) == 21)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -1 : -2);
                    continue;
                }

                s[encode(bit, val)][money] = encode(bit + 1, bitwise[money][bit + 1]);
            }
        }
    }
    
    return s;
}

Compilation message

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int bit = 0 ; bit < divide.size() ; ++bit)
      |                        ~~~~^~~~~~~~~~~~~~~
prison.cpp:110:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |                 if (bitwise[money].size() <= bit)
      |                     ~~~~~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 10 ms 1460 KB Output is correct
6 Correct 12 ms 1804 KB Output is correct
7 Correct 11 ms 1820 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 9 ms 1492 KB Output is correct