# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1212214 | NValchanov | 죄수들의 도전 (IOI22_prison) | C++20 | 0 ms | 0 KiB |
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector < vector < int > > devise_strategy(int n)
{
int lg = 1;
int cur = 2;
while(cur <= n)
{
lg++;
cur *= 2;
}
vector < vector < int > > ans;
ans.resize(3 * lg + 1);
for(int reads = 0; reads <= 3 * lg; reads++)
{
ans[reads].resize(n + 1, 0);
}
for(int reads = 0; reads <= 3 * lg; reads++)
{
int whole = reads / 3;
int remainder = i % 3;
if(remainder == 0)
{
ans[reads][0] = 0; // cheta A
for(int sees = 1; sees <= n; sees++)
{
int which = lg - whole - 1;
bool bitb = (bool)(sees & (1 << which));
int writes = reads + bitb + 1; // pri A % 2 == 0 -> napisanoto + 1 (ostatuk 1), pri A % 2 == 1 -> napisanoto + 2 (ostatuk 2)
ans[reads][sees] = writes;
}
}
else
{
ans[reads][0] = 1; // cheta B
for(int sees = 1; sees <= n; sees++)
{
bool bita = remainder - 1; // ostatuk na napisanoto 1 -> A % 2 == 0, pri ostatuk na napisanoto 2 -> A % 2 == 1
int which = lg - whole - 1;
bool bitb = (bool)(sees & (1 << which));
if(bita < bitb) // A < B
ans[reads][sees] = -1;
else if(bita > bitb) // A > B
ans[reads][sees] = -2;
else // nqmame dostatuchno info
ans[reads][sees] = 3 * (whole + 1);
}
}
}
return ans;
}