| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 852833 | weajink | 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.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//Autor: Michał Szeliga
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...) {}
#endif
#define read(...) debug((void)!freopen(__VA_ARGS__,"r",stdin););
int pt = 0;
pair<int,int> przedzial[5001];
vector<int> synowie[5001];
int dokogo[5001][30];
int ktorysyn[5001];
int kiedyodpowiedz[5001];
bool koniec[5001][30];
void policz(int v, int poziom, int a, int b){
przedzial[v] = {a,b};
//if (poziom == 8 && b-a > 1) cout<<v<<" # "<<poziom<<" "<<a<<" "<<b<<"\n";
for (int i = a; i <= b; i++) dokogo[i][poziom] = v;
for (int j = poziom+1; j < 30; j++){
dokogo[a][j] = dokogo[b][j] = v;
koniec[a][j] = koniec[b][j] = 1;
}
//if (a <= 16 && 16 <= b) cout<<v<<" # "<<" "<<poziom<<": "<<a<<" "<<b<<"\n";
if (poziom < 5){
a++;b--;
if (a > b) return;
int c = a+(b-a)/3;
int d = b-(b-a)/3;
if (a <= c){
synowie[v].push_back(++pt);
ktorysyn[pt] = 0;
policz(pt,poziom+1,a,c);
}
if (c+1 <= d){
synowie[v].push_back(++pt);
ktorysyn[pt] = 1;
policz(pt,poziom+1,c+1,d);
}
if (d+1 <= b){
synowie[v].push_back(++pt);
ktorysyn[pt] = 2;
policz(pt,poziom+1,d+1,b);
}
}else{
a++;
b--;
if (a > b) return;
int c = (a+b)/2;
if (a <= c){
synowie[v].push_back(++pt);
ktorysyn[pt] = 0;
policz(pt,poziom+1,a,c);
}
if (c+1 <= b){
synowie[v].push_back(++pt);
ktorysyn[pt] = 1;
policz(pt,poziom+1,c+1,b);
}
}
}
vector<vector<int> > devise_strategy(int N){
policz(++pt,0,1,5000);
vector<vector<int> > tab(21);
vector<int> jakipoziom(21);
vector<int> ktoryziomek(21);
jakipoziom[0] = ktoryziomek[0] = 0;
for (int i = 0; i < 5; i++){
for (int j = 0; j < 3; j++){
jakipoziom[1+i*3+j] = i+1;
ktoryziomek[1+i*3+j] = j;
}
}
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
jakipoziom[16+i*2+j] = i+6;
ktoryziomek[16+i*2+j] = j;
}
}
jakipoziom[20] = 8;
ktoryziomek[20] = 0;
for (int liczba = 0; liczba < 21; liczba++){
int poziom = jakipoziom[liczba];
int ktory = ktoryziomek[liczba];
tab[liczba].resize(N+1);
tab[liczba][0] = poziom%2;
int Moj = -1;
int Niemoj = -2;
if (poziom%2){
Moj = -2;
Niemoj = -1;
}
for (int worek = 1; worek <= N; worek++){
int wierzcholek = dokogo[worek][poziom];
int a = przedzial[wierzcholek].first;
int b = przedzial[wierzcholek].second;
/*if (worek == 7){
cout<<liczba<<" ### "<<"poziom: "<<poziom<<" "<<wierzcholek<<" "<<ktorysyn[wierzcholek]<<" "<<ktory<<"\n";
}*/
if (ktorysyn[wierzcholek] != ktory && !koniec[worek][poziom]){
if (ktorysyn[wierzcholek] < ktory) tab[liczba][worek] = Moj;
else tab[liczba][worek] = Niemoj;
}else if (worek == a){
tab[liczba][worek] = Moj;
}else if (worek == b){
tab[liczba][worek] = Niemoj;
}else{
if (poziom == 7){
tab[liczba][worek] = 20;
continue;
}
int nowaliczba = liczba;
while (jakipoziom[nowaliczba] == jakipoziom[liczba]) nowaliczba++;
/* if (worek == 10 && liczba == 16){
cout<<"Amongas\n";
}*/
tab[liczba][worek] = nowaliczba;
if (synowie[wierzcholek].size() > 1){
auto przedzial1 = przedzial[synowie[wierzcholek][1]];
/*if (worek == 10 && liczba == 16){
cout<<przedzial1.first<<" ";
}*/
if (przedzial1.first <= worek) tab[liczba][worek]++;
}
if (synowie[wierzcholek].size() > 2){
auto przedzial2 = przedzial[synowie[wierzcholek][2]];
/*if (worek == 10 && liczba == 16){
cout<<przedzial2.first<<" ";
}*/
if (przedzial2.first <= worek) tab[liczba][worek]++;
}
/*if (worek == 10 && liczba == 16){
cout<<"\n";
}*/
}
/*if (worek == 3){
cout<<liczba<<" "<<tab[liczba][worek]<<"\n";
}*/
}
}
return tab;
}
int main(){
//ios_base::sync_with_stdio(0);
// cin.tie(0);
int i;
vector<vector<int> > strategia = devise_strategy(5000);
/*for (i = 1; i <= 5000; i++){
for (int j = 0; j < 9; j++) cout<<dokogo[i][j]<<" ";
cout<<"\n";
}*/
int N,A,B;
cin>>N>>A>>B;
int tablica = 0;
//return 0;
while (1){
int ruch = strategia[tablica][0];
int val = 0;
if (ruch == 0) val = A;
else val = B;
int ruch2 = strategia[tablica][val];
cout<<"Tab: "<<tablica<<" ktory: "<<ruch<<" val: "<<val<<" # "<<strategia[tablica][val]<<"\n";
tablica = strategia[tablica][val];
if (ruch2 < 0) exit(0);
}
return 0;
}