This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
**/
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++)
| ~~^~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
