Submission #852835

#	Time	Username	Problem	Language	Result	Execution time	Memory
852835		weajink	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	2084 KiB

prison

#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);
    
    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;
}*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90