#include "prison.h"
#include <vector>
using namespace std;
const int MAXLOG = 8;
int p3[MAXLOG];
vector < vector < int > > devise_strategy(int n)
{
int lg = 1;
int cur = 3;
while(cur <= n)
{
lg++;
cur *= 3;
}
p3[0] = 1;
for(int i = 1; i < MAXLOG; i++)
{
p3[i] = p3[i - 1] * 3;
}
vector < vector < int > > ans;
ans.resize(3 * lg - 2 + 1);
for(int i = 0; i <= 3 * lg - 2; i++)
{
ans[i].resize(n + 1, 0);
}
for(int sees = 1; sees <= n; sees++)
{
int trit = sees / p3[lg - 1];
ans[0][sees] = trit + 1;
}
for(int reads = 1; reads <= 3 * lg - 2; reads++)
{
int whole = reads / 3 + (bool)(reads % 3);
if(whole % 2 == 0)
ans[reads][0] = 0;
else
ans[reads][0] = 1;
for(int sees = 1; sees <= n; sees++)
{
int trita;
if(whole == lg)
trita = 1;
else
trita = (reads + 2) % 3;
int which = lg - whole;
int tritb = (sees / p3[which]) % 3;
if(trita < tritb)
{
if(whole % 2 == 0)
ans[reads][sees] = -2;
else
ans[reads][sees] = -1;
}
else if(trita > tritb)
{
if(whole % 2 == 0)
ans[reads][sees] = -1;
else
ans[reads][sees] = -2;
}
else if(whole == lg - 1)
{
if(sees % 3 == 1)
{
ans[reads][sees] = 3 * whole + 1;
}
else
{
int cur = whole;
if(sees % 3 == 0)
cur++;
if(cur % 2 == 1)
ans[reads][sees] = -1;
else
ans[reads][sees] = -2;
}
}
else
{
if(whole == lg)
{
ans[reads][sees] = 0;
}
else
{
int nxttrit = (sees / p3[which - 1]) % 3;
int writes = 3 * whole + nxttrit + 1;
ans[reads][sees] = writes;
}
}
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |