제출 #979105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979105		andrei_iorgulescu	죄수들의 도전 (IOI22_prison)	C++17	90 / 100	10 ms	1884 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(22);
    for (int i = 0; i < 22; i++)
        ans[i].resize(n + 1);
    ///A = (A - 1) / 4, B = (B - 1) / 4
    ans[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int xx = (i - 1) / 4;
        if (xx < 625)
            ans[0][i] = 1;
        else
            ans[0][i] = 2;
    }
    for (int i = 1; i <= 21; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int xx = (j - 1) / 4;
            int nm = xx;
            if (i >= 3)
                nm %= 625;
            if (i >= 5)
                nm %= 313;
            if (i >= 7)
                nm %= 157;
            if (i >= 9)
                nm %= 79;
            if (i >= 12)
                nm %= 27;
            if (i >= 15)
                nm %= 9;
            if (i >= 18)
                nm %= 3;
            if (i >= 1 and i <= 2)
            {
                ans[i][0] = 1;
                if (nm >= 625 and i == 1)
                    ans[i][j] = -1;
                else if (nm < 625 and i == 2)
                    ans[i][j] = -2;
                else
                {
                    if (nm % 625 < 313)
                        ans[i][j] = 3;
                    else
                        ans[i][j] = 4;
                }
            }
            else if (i >= 3 and i <= 4)
            {
                ans[i][0] = 0;
                if (nm >= 313 and i == 3)
                    ans[i][j] = -2;
                else if (nm < 313 and i == 4)
                    ans[i][j] = -1;
                else
                {
                    if (nm % 313 < 157)
                        ans[i][j] = 5;
                    else
                        ans[i][j] = 6;
                }
            }
            else if (i >= 5 and i <= 6)
            {
                ans[i][0] = 1;
                if (nm >= 157 and i == 5)
                    ans[i][j] = -1;
                else if (nm < 157 and i == 6)
                    ans[i][j] = -2;
                else
                {
                    if (nm % 157 < 79)
                        ans[i][j] = 7;
                    else
                        ans[i][j] = 8;
                }
            }
            else if (i >= 7 and i <= 8)
            {
                ans[i][0] = 0;
                if (nm >= 79 and i == 7)
                    ans[i][j] = -2;
                else if (nm < 79 and i == 8)
                    ans[i][j] = -1;
                else
                {
                    if (nm % 79 < 27)
                        ans[i][j] = 9;
                    else if (nm % 79 < 54)
                        ans[i][j] = 10;
                    else
                        ans[i][j] = 11;
                }
            }
            else if (i >= 9 and i <= 11)
            {
                ans[i][0] = 1;
                if ((nm < 27 and i >= 10) or (nm < 54 and i == 11))
                    ans[i][j] = -2;
                else if ((nm >= 54 and i <= 10) or (nm >= 27 and i == 9))
                    ans[i][j] = -1;
                else
                {
                    if (nm % 27 < 9)
                        ans[i][j] = 12;
                    else if (nm % 27 < 18)
                        ans[i][j] = 13;
                    else
                        ans[i][j] = 14;
                }
            }
            else if (i >= 12 and i <= 14)
            {
                ans[i][0] = 0;
                if ((nm < 9 and i >= 13) or (nm < 18 and i == 14))
                    ans[i][j] = -1;
                else if ((nm >= 18 and i <= 13) or (nm >= 9 and i == 12))
                    ans[i][j] = -2;
                else
                {
                    if (nm % 9 < 3)
                        ans[i][j] = 15;
                    else if (nm % 9 < 6)
                        ans[i][j] = 16;
                    else
                        ans[i][j] = 17;
                }
            }
            else if (i >= 15 and i <= 17)
            {
                ans[i][0] = 1;
                if ((nm < 3 and i >= 16) or (nm < 6 and i == 17))
                    ans[i][j] = -2;
                else if ((nm >= 6 and i <= 16) or (nm >= 3 and i == 15))
                    ans[i][j] = -1;
                else
                {
                    if (nm % 3 == 0)
                        ans[i][j] = 18;
                    else if (nm % 3 == 1)
                        ans[i][j] = 19;
                    else
                        ans[i][j] = 20;
                }
            }
            else if (i >= 18 and i <= 20)
            {
                ans[i][0] = 0;
                if ((nm < 1 and i >= 19) or (nm < 2 and i == 20))
                    ans[i][j] = -1;
                else if ((nm >= 2 and i <= 19) or (nm >= 1 and i == 18))
                    ans[i][j] = -2;
                else
                {
                    if ((j - 1) % 4 == 0)
                        ans[i][j] = -1;
                    else if ((j - 1) % 4 == 3)
                        ans[i][j] = -2;
                    else
                        ans[i][j] = 21;
                }
            }
            else
            {
                ans[i][0] = 1;
                if ((j - 1) % 4 <= 1)
                    ans[i][j] = -2;
                else
                    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
-> Optimizarea la final ar merge si in baza 4 eventual, sa fie 4log4(N) - 4 + 1, dar vine 4 * 7 - 4 + 1, prea mull
-> Still, eu pot zice ca vreau in 20 de operatii sa compar (cu posibila egalitate) doua numere pana la 1250
-> 1250 -> 625 -> 313 -> 157 -> 79 -> 27 -> 9 -> 3 -> 1 cu 2 * 4 + 3 * 4
-> Deci zic asa: ma uit la A = (A - 1), B = (B - 1), A = A / 4 si B = B / 4 (am doua numere intre 0 si 1249)
-> Folosesc primii 20 de biti ca sa compar prostiile astea, apoi, in caz de egalitate, eventual un bit ca sa compar A % 4 cu B % 4 (diferite)

**/

컴파일 시 표준 에러 (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: 80 / 90