#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> L[25], R[25], l[25], r[25], nothing;
vector<vector<int> > ans;
vector<vector<int> > devise_strategy(int n)
{
for (int i=0; i<=n; i++)
nothing.push_back(0);
for (int i=0; i<=20; i++)
ans.push_back(nothing);
l[0].push_back(1);
r[0].push_back(5102);
int cnt=0;
for (int i=0; i<=20; i++)
{
// cout << "i=" << i << '\n';
for (int j=0; j<l[i].size(); j++)
{
if (i<=15)
{
l[cnt+1].push_back(l[i][j]+1);
r[cnt+1].push_back((l[i][j]*2+r[i][j])/3);
l[cnt+2].push_back((l[i][j]*2+r[i][j])/3+1);
r[cnt+2].push_back((l[i][j]+r[i][j]*2)/3);
l[cnt+3].push_back((l[i][j]+r[i][j]*2)/3+1);
r[cnt+3].push_back(r[i][j]-1);
}
else
{
l[cnt+1].push_back(l[i][j]+1);
r[cnt+1].push_back((l[i][j]+r[i][j])/2);
l[cnt+2].push_back((l[i][j]+r[i][j])/2+1);
r[cnt+2].push_back(r[i][j]-1);
}
}
if (i%3==1)
{
R[i].push_back(i+1);
if (i!=19)
R[i].push_back(i+2);
}
else if (i%3==2)
{
L[i].push_back(i-1);
if (i!=20)
R[i].push_back(i+1);
}
else
{
if (i)
{
L[i].push_back(i-2);
L[i].push_back(i-1);
}
cnt+=3;
}
}
cnt=0;
for (int i=0; i<=20; i++)
{
// cout << "i=" << i << '\n';
for (int j=0; j<l[i].size(); j++)
{
if (l[i][j]<=n)
ans[i][l[i][j]]=-1-ans[i][0];
if (r[i][j]<=n)
ans[i][r[i][j]]=-2+ans[i][0];
for (int k=l[i][j]+1; k<=min(n, r[i][j]-1); k++)
{
if (k<=n)
{
if (i<=15)
{
if (k<=(l[i][j]*2+r[i][j])/3)
ans[i][k]=cnt+1;
else if (k<=(l[i][j]+r[i][j]*2)/3)
ans[i][k]=cnt+2;
else
ans[i][k]=cnt+3;
}
else
{
if (k<=(l[i][j]+r[i][j])/2)
ans[i][k]=cnt+1;
else
ans[i][k]=cnt+2;
}
}
}
}
if (i)
{
for (int z=0; z<L[i].size(); z++)
{
int u=L[i][z];
// cout << "u=" << u << '\n';
for (int j=0; j<l[u].size(); j++)
{
if (!z && l[u][j]-1<=n)
ans[i][l[u][j]-1]=-1-ans[i][0];
for (int k=l[u][j]; k<=min(n, r[u][j]); k++)
ans[i][k]=-1-ans[i][0];
}
}
if (L[i].empty())
{
for (int j=0; j<l[i].size(); j++)
if (l[i][j]-1<=n)
ans[i][l[i][j]-1]=-1-ans[i][0];
}
for (int z=0; z<R[i].size(); z++)
{
int u=R[i][z];
// cout << "u=" << u << '\n';
for (int j=0; j<l[u].size(); j++)
{
if (z==R[i].size()-1 && r[u][j]+1<=n)
ans[i][r[u][j]+1]=-2+ans[i][0];
for (int k=l[u][j]; k<=min(n, r[u][j]); k++)
ans[i][k]=-2+ans[i][0];
}
}
if (R[i].empty())
{
for (int j=0; j<l[i].size(); j++)
if (r[i][j]+1<=n)
ans[i][r[i][j]+1]=-2+ans[i][0];
}
}
if (i%3==0)
{
ans[cnt+1][0]=ans[i][0]^1;
ans[cnt+2][0]=ans[i][0]^1;
if (i!=18)
ans[cnt+3][0]=ans[i][0]^1;
cnt+=3;
}
}
// for (int i=0; i<=10; i++)
// {
// for (int j=0; j<=10; j++)
// cout << ans[i][j] << ' ';
// cout << '\n';
// }
return ans;
}
Compilation message
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:18:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (int j=0; j<l[i].size(); j++)
| ~^~~~~~~~~~~~
prison.cpp:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int j=0; j<l[i].size(); j++)
| ~^~~~~~~~~~~~
prison.cpp:94:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int z=0; z<L[i].size(); z++)
| ~^~~~~~~~~~~~
prison.cpp:98:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int j=0; j<l[u].size(); j++)
| ~^~~~~~~~~~~~
prison.cpp:108:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int j=0; j<l[i].size(); j++)
| ~^~~~~~~~~~~~
prison.cpp:112:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int z=0; z<R[i].size(); z++)
| ~^~~~~~~~~~~~
prison.cpp:116:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int j=0; j<l[u].size(); j++)
| ~^~~~~~~~~~~~
prison.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | if (z==R[i].size()-1 && r[u][j]+1<=n)
| ~^~~~~~~~~~~~~~~
prison.cpp:126:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int j=0; j<l[i].size(); j++)
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
6 ms |
852 KB |
Output is correct |
5 |
Correct |
9 ms |
1296 KB |
Output is correct |
6 |
Correct |
12 ms |
1496 KB |
Output is correct |
7 |
Correct |
10 ms |
1468 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
5 ms |
724 KB |
Output is correct |
12 |
Correct |
8 ms |
1236 KB |
Output is correct |