#include <bits/stdc++.h>
#include "prison.h"
//#include "grader.cpp"
using namespace std;
typedef pair<int,int> pii;
int dp[22];
int take[22];
pii nivpoz[22];
int cod[105][105];
int poz[6005][22];
int split[105];
// -1 -> small
// -2 -> big
void build(int niv,int l,int r)
{
poz[l][niv+1]=-1;
poz[r][niv+1]=-2;
if(split[niv]==0)
return;
l++;
r--;
int nr=split[niv];
int lg=(r-l+1)/nr;
for(int i=l;i<=r;i++)
{
int cat=1+(i-l)/lg;
poz[i][niv+1]=cat;
}
int i=l;
while(i<=r)
{
build(niv+1,i,i+lg-1);
i+=lg;
}
}
std::vector<std::vector<int>> devise_strategy(int N)
{
int n=N;
dp[0]=2;
for(int i=1;i<=20;i++)
{
for(int j=1;j<=i;j++)
{
int val=j*dp[i-j]+2;
if(val>dp[i])
{
dp[i]=val;
take[i]=j;
}
}
}
int op=20;
int niv=0;
int x=0;
while(op>0)
{
split[niv]=take[op];
niv++;
for(int i=1;i<=take[op];i++)
{
x++;
nivpoz[x]={niv,i};
cod[niv][i]=x;
}
op-=take[op];
}
build(0,1,dp[20]);
vector<vector<int>> sol;
for(int board=0;board<=20;board++)
{
vector<int> v;
if(board==0)
{
v.push_back(0);
for(int i=1;i<=n;i++)
{
if(poz[i][1]==-1)
{
v.push_back(-1);
continue;
}
if(poz[i][1]==-2)
{
v.push_back(-2);
continue;
}
int p=poz[i][1];
int c=cod[1][p];
v.push_back(c);
}
sol.push_back(v);
continue;
}
niv=nivpoz[board].first;
int p=nivpoz[board].second;
if(niv%2==1)
{
v.push_back(1);
for(int i=1;i<=n;i++)
{
if(poz[i][niv]==-1)
{
v.push_back(-2);
continue;
}
if(poz[i][niv]==-2)
{
v.push_back(-1);
continue;
}
if(poz[i][niv]<p)
{
v.push_back(-2);
continue;
}
if(poz[i][niv]>p)
{
v.push_back(-1);
continue;
}
if(poz[i][niv+1]==-1)
{
v.push_back(-2);
continue;
}
if(poz[i][niv+1]==-2)
{
v.push_back(-1);
continue;
}
int c=cod[niv+1][poz[i][niv+1]];
v.push_back(c);
}
sol.push_back(v);
continue;
}
else
{
v.push_back(0);
for(int i=1;i<=n;i++)
{
if(poz[i][niv]==-1)
{
v.push_back(-1);
continue;
}
if(poz[i][niv]==-2)
{
v.push_back(-2);
continue;
}
if(poz[i][niv]<p)
{
v.push_back(-1);
continue;
}
if(poz[i][niv]>p)
{
v.push_back(-2);
continue;
}
if(poz[i][niv+1]==-1)
{
v.push_back(-1);
continue;
}
if(poz[i][niv+1]==-2)
{
v.push_back(-2);
continue;
}
int c=cod[niv+1][poz[i][niv+1]];
v.push_back(c);
}
sol.push_back(v);
continue;
}
}
return sol;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
852 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
5 ms |
1108 KB |
Output is correct |
5 |
Correct |
8 ms |
1312 KB |
Output is correct |
6 |
Correct |
9 ms |
1492 KB |
Output is correct |
7 |
Correct |
10 ms |
1504 KB |
Output is correct |
8 |
Correct |
2 ms |
760 KB |
Output is correct |
9 |
Correct |
2 ms |
820 KB |
Output is correct |
10 |
Correct |
2 ms |
852 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
8 ms |
1364 KB |
Output is correct |