| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 638008 | huutuan | Prisoner Challenge (IOI22_prison) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define taskname "cf"
using namespace std;
#ifndef beez
#define cerr if (0) cerr
#endif
#define int long long
#define defll
#ifdef defll
#define sumof(a) accumulate(all(a), 0ll)
#define bit(x, i) (((x)>>(i))&1ll)
#define lsb(a) __builtin_ctzll(a)
#define msb(a) (63-__builtin_clzll(a))
#define cntbit(a) __builtin_popcountll(a)
#else
#define sumof(a) accumulate(all(a), 0)
#define bit(x, i) (((x)>>(i))&1)
#define lsb(a) __builtin_ctz(a)
#define msb(a) (31-__builtin_clz(a))
#define cntbit(a) __builtin_popcount(a)
#endif
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) ((int) a.size())
#define ret(a) return cout << (a) << "\n", void()
#define NEVER freopen(
#define GONNA taskname
#define GIVE ".inp", "r"
#define YOU
#define UP , stdin);
#define LET ".out", "w"
#define DOWN , stdout);
#define RUN ".err"
#define AROUND , "w"
#define AND , stderr
#define DESERT );
template<typename A, typename B>
istream& operator>>(istream& in, pair<A, B> &v){
in >> v.first >> v.second;
return in;
}
template<typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B> &v){
out << v.first << " " << v.second << " ";
return out;
}
template<class Con, class=decltype(declval<Con>().begin())>
typename enable_if<!is_same<Con, string>::value, istream&>::type
operator>>(istream& in, Con& con){
for (auto it=con.begin(); it!=con.end(); ++it) in >> *it;
return in;
}
template<class Con, class=decltype(declval<Con>().begin())>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con){
if (con.empty()) return out;
auto v=*con.begin();
bool p=is_class<decltype(v)>::value;
for (auto it=con.begin(), it2=--con.end(); it!=con.end(); ++it) out << *it << (!p?(it==it2?"\n":" "):"");
return out;
}
vector<int> base={3, 3, 3, 3, 3, 2, 2, 1};
vector<vector<int>> v;
vector<vector<int>> states={{0}, {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}, {13, 14, 15}, {16, 17}, {18, 19}, {20}};
int n;
vector<int> divide(int depth, int l, int r){
int t=base[depth];
if (t==1) return {r};
if (t==2) return {(l+r)/2, r};
if (t==3) return {l+(r-l)/3, l+(r-l)/3*2, r};
}
void dnc(int depth, int l, int r, bool box){
if (l>r) return;
if (l==r){
v[states[depth][0]][0]=box;
for (int j=1; j<=n; ++j) if (j<l) v[states[depth][0]][j]=-1-box; else v[states[depth][0]][j]=-2+box;
return;
}
auto vv=divide(depth, l+1, r-1);
while (sz(vv)>1 && vv.back()<=vv[sz(vv)-2]) vv.pop_back();
for (int i=0; i<sz(states[depth]); ++i){
v[states[depth][i]][0]=box;
int id=0;
for (int j=1; j<=n; ++j){
if (j<=l) v[states[depth][i]][j]=-1-box;
else if (j>=r) v[states[depth][i]][j]=-2+box;
else{
if (j>vv[id]) ++id;
if (i<id) v[states[depth][i]][j]=-1-box;
else if (i>id) v[states[depth][i]][j]=-2+box;
else{
auto vvv=divide(depth+1, i?vv[i-1]:l+1, vv[i]);
while (sz(vvv)>1 && vvv.back()<=vvv[sz(vvv)-2]) vvv.pop_back();
int t=upper_bound(vvv.begin(), vvv.end(), j)-vvv.begin()-1;
t=max(t, 0ll);
v[states[depth][i]][j]=states[depth+1][t];
}
}
}
}
for (int i=0; i<sz(vv); ++i) dnc(depth+1, i?vv[i-1]:l+1, vv[i], box^1);
}
vector<vector<int>> devise_strategy(int N){
n=N;
vector<vector<int>>(21, vector<int>(n+1)).swap(v);
dnc(0, 1, n, 0);
return v;
}
void solve(){
cout << devise_strategy(243);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef beez
NEVER GONNA GIVE YOU UP
NEVER GONNA LET YOU DOWN
NEVER GONNA RUN AROUND AND DESERT YOU
#endif // beez
int ntests=1;
// cin >> ntests;
while (ntests--) solve();
return 0;
}