제출 #978067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978067		andrei_iorgulescu	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	12 ms	2396 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(25);
    for (int i = 0; i < 25; 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 <= 24; 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
                    ans[i][j] = ((i - 1) / 3) * 3 + 3 + 1 + trit(j,poztrit - 1);
            }
        }
        else
        {
            ans[i][0] = 0;
            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] = -2;
                    else
                        ans[i][j] = -1;
                }
                else
                    ans[i][j] = ((i - 1) / 3) * 3 + 3 + 1 + trit(j,poztrit - 1);
            }
        }
        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

**/

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