Submission #852823

#	Time	Username	Problem	Language	Result	Execution time	Memory
852823		weajink	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	6 ms	1372 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];

void policz(int v, int poziom, int a, int b){
	przedzial[v] = {a,b};
	for (int i = a; i <= b; i++) dokogo[i][poziom] = v;
	//if (a <= 3800 && 3800 <= b) cout<<v<<" # "<<a<<" "<<b<<"\n";
	if (poziom < 200){
		for (int j = poziom; j < 30; j++) dokogo[a][j] = dokogo[b][j] = v;
		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--;
		int c = (a+b)/2;
		if (a <= c){
			synowie[v].push_back(++pt);
			policz(pt,poziom+1,a,c);
		}
		if (c+1 <= b){
			synowie[v].push_back(++pt);
			policz(pt,poziom+1,c+1,b);
		}
	}
} 

vector<vector<int> > devise_strategy(int N){
	policz(++pt,0,1,5000);
	vector<vector<int> > tab(22);
	for (int liczba = 0; liczba < 22; liczba++){
		
		int poziom = (liczba+2)/3;
		int ktory = 0;
		if (liczba != 0){
			ktory = (liczba-1)%3;
		}
		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 == 3800 && liczba == 2){
				cout<<wierzcholek<<" "<<ktorysyn[wierzcholek]<<" "<<ktory<<"\n";
			}*/
			if (ktorysyn[wierzcholek] != ktory){
				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{
				
				tab[liczba][worek] = 1+3*poziom;
				if (synowie[wierzcholek].size() > 1){
					auto przedzial1 = przedzial[synowie[wierzcholek][1]];
					if (przedzial1.first <= worek) tab[liczba][worek]++;
				}
				if (synowie[wierzcholek].size() > 2){
					auto przedzial2 = przedzial[synowie[wierzcholek][2]];
					if (przedzial2.first <= worek) tab[liczba][worek]++;
				}
			}
		}
	}
	return tab;
}


/*int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    int i;
	policz(++pt,0,1,5000);
	for (i = 1; i <= 5000; i++){
		cout<<i<<" # ";
		for (int j = 0; j <= 7; j++) cout<<dokogo[i][j]<<" ";
		cout<<"\n";
	}
    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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 90