Submission #978085

#	Time	Username	Problem	Language	Result	Execution time	Memory
978085		andrei_iorgulescu	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	2140 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"

using namespace std;

int n = 5000;
int real_N;

int trit(int x,int pos)
{
    for (int i = 1; i <= pos; i++)
        x /= 3;
    return x % 3;
}

vector<vector<int>> get_real_ans(vector<vector<int>> ans)
{
    vector<vector<int>> real_ans;
    real_ans.resize(ans.size());
    for (int i = 0; i < ans.size(); i++)
        for (int j = 0; j < real_N + 1; j++)
            real_ans[i].push_back(ans[i][j]);
    return real_ans;
}

vector<vector<int>> devise_strategy(int N)
{
    real_N = N;
    vector<vector<int>>ans;
    ans.resize(23);
    for (int i = 0; i < 23; i++)
        ans[i].resize(n + 1);
    ans[0][0] = 0;
    for (int i = 1; i <= n; i++)
        ans[0][i] = 1 + trit(i,7);
    for (int i = 1; i <= 22; i++)
    {
        if (((i - 1) / 3) % 2 == 0)
        {
            ///primul numar e (i - 1) % 3, ma uit la al doilea
            ans[i][0] = 1;
            for (int j = 1; j <= n; j++)
            {
                int poztrit = 7 - (i - 1) / 3;
                int curtrit = trit(j,poztrit);
                if (curtrit != (i - 1) % 3)
                {
                    if (curtrit > (i - 1) % 3)
                        ans[i][j] = -1;
                    else
                        ans[i][j] = -2;
                }
                else
                {
                    if (i < 19)
                        ans[i][j] = ((i - 1) / 3) * 3 + 3 + 1 + trit(j,poztrit - 1);
                    else
                    {
                        //if (i == 20 and j == 4)
                          //  cout << "yup" << endl;
                        if (trit(j,poztrit - 1) == 0)
                            ans[i][j] = -2;
                        else if (trit(j,poztrit - 1) == 2)
                            ans[i][j] = -1;
                        else
                            ans[i][j] = 22;
                    }
                }
            }
        }
        else
        {
            ans[i][0] = 0;
            for (int j = 1; j <= n; j++)
            {
                int poztrit = 7 - (i - 1) / 3;
                int curtrit = trit(j,poztrit);
                if (i < 22)
                {
                    if (curtrit != (i - 1) % 3)
                    {
                        if (curtrit > (i - 1) % 3)
                            ans[i][j] = -2;
                        else
                            ans[i][j] = -1;
                    }
                    else
                        ans[i][j] = ((i - 1) / 3) * 3 + 3 + 1 + trit(j,poztrit - 1);
                }
                else
                {
                    if (curtrit == 0)
                        ans[i][j] = -1;
                    else
                        ans[i][j] = -2;
                }
            }
        }
        /*if (i == 22)
            for (int j = 1; j <= n; j++)
                if (ans[i][j] >= 0)
                    ans[i][j] = -1;*/
    }
    vector<vector<int>> real_ans = get_real_ans(ans);
    return real_ans;
}

/**
Idee sqrt -> Iau un B = sqrt(N), intreb primul numar si raspund cu 1 + x / B, intreb al doilea cand vad ceva sub N / B si daca da alt x / B raspund
          -> Daca da acelasi x / B, pun un N / B + 2 si il rog pe primul sa intrebe x % B punand N / B + 3 + x % B, la care al doilea vede si compara x % B

Asta foloseste gen 2sqrt(N), 10p
**/


/**
Idee biti -> Vad 0, intreb de primul numar si ii pun 1 + primul bit. Al doilea vede asta si compara primii biti. La egalitate, scrie 3 si se repeta procesul
          -> Candva, vor da bitii diferiti

Asta foloseste 3logN = 39, 26.5p
**/

/**
Idee biti based -> Vad 0, intreb primul numar si ii scriu 1 + primul bit. Al doilea citeste 1 / 2, compara cu primul bit din al doilea numar
                -> Daca e diferit de primul bit din primul numar, e gata, altfel scrie 3 / 4 reprezentand al doilea bit din al doilea numar
Asta foloseste 2logN = 26, 42p
**/

/**
Optimizari:
-> Pot folosi baza 3 si fac x = 3log3(N) = 3 * 8 = 24, 65p
-> Pot sa tai putin de la ultimul bit cu o chestie actually cute: cand primul intreaba, daca e 0 sau 2 atunci clar stiu rez (fiind diferite), altfel pun +1
-> Cu ultima optimizare fac x = 3log3(N) - 3 + 1 = 22, 80p

**/

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > get_real_ans(std::vector<std::vector<int> >)':
prison.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < ans.size(); i++)
      |                     ~~^~~~~~~~~~~~

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