# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1169769 | thelegendary08 | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
using namespace std;
vi tern(int x){
int cur = 1;
vi ret;
while(x > 0){
ret.pb(x % (cur * 3) / cur);
x -= (x % (cur * 3));
cur *= 3;
}
while(ret.size() < 8)ret.pb(0);
reverse(ret.begin(), ret.end());
return ret;
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vi>v(23, vi(N+1));
v[0][0] = 0;
FOR(i, 1, N+1){
vi cur = tern(i);
v[0][i] = 1 + cur[0];
}
FOR(dig, 1, 8){
if(dig % 2 == 1){
v[dig * 3 - 2][0] = 1;
v[dig * 3 - 1][0] = 1;
v[dig * 3][0] = 1;
}
else{
v[dig * 3 - 2][0] = 0;
v[dig * 3 - 1][0] = 0;
v[dig * 3][0] = 0;
}
//v[2][1] is -2
//v[1][2] is -1
FOR(i, 1, N+1){
vi cur = tern(i);
f0r(j, 3){
if(dig != 8){
if(cur[dig-1] < j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
}
else if(cur[dig-1] > j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
}
else{
if(dig != 7)v[(dig - 1) * 3 + 1 + j][i] = dig * 3 + 1 + cur[dig];
else{
if(cur[dig] == 0){
int thing = 0;
f0r(j, 22){
if(v[j][0] == 1 && v[j][i] == -2){
thing = j; break;
}
}
v[(dig - 1) * 3 + 1 + j][i] = thing;
}
else if(cur[dig] == 2){
int thing = 0;
f0r(j, 22){
if(v[j][0] == 1 && v[j][i] == -1){
thing = j; break;
}
}
v[(dig - 1) * 3 + 1 + j][i] = thing;
}
else{
v[(dig - 1) * 3 + 1 + j][i] = 22;
}
}
}
}
else{
if(cur[dig-1] < j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
}
else if(cur[dig-1] > j){
v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
}
}
}
}
}
v[22][0] = 0;
FOR(i, 1, N+1){
vi cur = tern(i);
if(cur[7] == 0){
v[22][i] = -1;
}
else v[22][i] = -2;
}
/*
f0r(i, 23){
f0r(j, 11)cout<<v[i][j]<<' ';
cout<<'\n';
}
*/
return v;
}