Submission #935270

#	Time	Username	Problem	Language	Result	Execution time	Memory
935270		freedommo33	Chameleon's Love (JOI20_chameleon)	C++17	4 / 100	32 ms	812 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"
#include <vector>
#define query Query
#define answer Answer
constexpr int M = 1005;
using namespace std;
vector<vector<int>> sasiedzi(M);
vector<vector<int>> g(M);
vector<vector<int>> g2(M);
int syn[M];
bool uzyte[M];
int kolor[M];
int rep[M];
int sajz[M];
vector<int> spojna[2];

void dfs(int v, int k){
	kolor[v] = k;
	for(auto i:sasiedzi[v]) if(kolor[i]==0 || kolor[i]==k){
		if(k==1) dfs(i, 2);
		else	 dfs(i, 1);	
	}
}

int ilews(int p, int k, int numer, int koniec){
	vector<int> v;
	for(int i=p; i<=k; i++) v.push_back(spojna[numer][i-1]);
	if(koniec!=0) v.push_back(koniec);
	if(v.size()==0) return 0;
	return query(v);	
}
int numero;
int bs(int koniec){
	int temp1 = ilews(1, spojna[0].size(), 0, 0);
	int temp2 = ilews(1, spojna[0].size(), 0, koniec);
	//cout<<temp1<<" "<<temp2<<endl;
	int numer = 0;
	if(temp1 < temp2) numer = 1;
	temp1 = ilews(1, spojna[1].size(), 1, 0);
	temp2 = ilews(1, spojna[1].size(), 1, koniec);
	//cout<<"SPOJNA: "<<numer<<endl;
	if(temp1 < temp2 && numer==1) return -1;
	int p = 1, k = spojna[numer].size(), mid;
	while(p<k){
		mid = (p+k)/2;
		temp1 = ilews(p, mid, numer, 0);
		temp2 = ilews(p, mid, numer, koniec);
		if(temp1!=temp2) p = mid + 1;
		else	k = mid;
	}
	numero = numer;
	return p-1;
}

void Solve(int n) {
	for(int i=1; i<=2*n; i++){
		int aktKolor = 1;
		int wyn = bs(i);
		vector<int> doDodania;
		//cout<<i<<" wyn: "<<wyn<<endl;
		//cout<<endl;
		while(wyn!=-1){
			sasiedzi[i].push_back(spojna[numero][wyn]);
			//cout<<i<<"->"<<spojna[numero][wyn]<<endl;
			sasiedzi[spojna[numero][wyn]].push_back(i);
			if(kolor[spojna[numero][wyn]] == 1) aktKolor=2;
			else if(kolor[spojna[numero][wyn]] == 2) aktKolor=1;
			doDodania.push_back(spojna[numero][wyn]);
			spojna[numero].erase(spojna[numero].begin() + wyn);
			wyn = bs(i);
			//cout<<"wyn: "<<wyn<<endl;
		}
		for(auto j:doDodania){
			if(aktKolor==2 && (kolor[j]==2 || kolor[j]==0)) dfs(j, 1);
			else if(aktKolor==1 && (kolor[j]==1 || kolor[j]==0)) dfs(j, 2);
		}
		spojna[0].clear();
		spojna[1].clear();
		kolor[i] = aktKolor;
		for(int j=1; j<=2*n; j++){
			if(kolor[j]==1) spojna[0].push_back(j);
			if(kolor[j]==2) spojna[1].push_back(j);
		}
		/*for(int j=1; j<=2*n; j++) cout<<j<<" ";
		cout<<endl;
		for(int j=1; j<=2*n; j++) cout<<kolor[j]<<" ";
		cout<<endl<<endl;
		cout<<"S0: ";
		for(auto i:spojna[0]) cout<<i<<" ";
		cout<<endl;
		cout<<"S1: ";
		for(auto i:spojna[1]) cout<<i<<" ";
		cout<<endl;*/
	}	
	/*cout<<endl;
	for(int i=1; i<=2*n; i++){
		cout<<i<<": ";
		for(auto j:sasiedzi[i]) cout<<j<<" ";
		cout<<endl;
	}
	cout<<endl;
	cout<<"XD"<<endl;*/
	for(int i=1; i<=n*2; i++){
		if(sasiedzi[i].size()!=1){
			//cout<<i<<" "<<sasiedzi[i][0]<<" "<<sasiedzi[i][1]<<" "<<sasiedzi[i][2]<<endl;
			if(query({i, sasiedzi[i][0], sasiedzi[i][1]})==1) syn[i] = sasiedzi[i][2];
			if(query({i, sasiedzi[i][0], sasiedzi[i][2]})==1) syn[i] = sasiedzi[i][1];
			if(query({i, sasiedzi[i][2], sasiedzi[i][1]})==1) syn[i] = sasiedzi[i][0];
		}
	}
	//cout<<"XD"<<endl;
	for(int i=1; i<=n*2; i++){
		if(syn[i]!=0){
			g[i].push_back(syn[i]);
			g[syn[i]].push_back(i);
		}
	}
	for(int i=1; i<=n*2; i++){
		sort(g[i].begin(), g[i].end());
		if(syn[i]==0){
			if(uzyte[min(i, sasiedzi[i][0])] == 0){
				uzyte[min(i, sasiedzi[i][0])] = 1;
				answer(i, sasiedzi[i][0]);
			}
		}
		else{
			if(g[i][0] == sasiedzi[i][0] && g[i][1] == sasiedzi[i][1]){
				if(uzyte[min(i, sasiedzi[i][2])] == 0){
					uzyte[min(i, sasiedzi[i][2])] = 1;
					answer(i, sasiedzi[i][2]);
				}
			}
			else if(g[i][0] == sasiedzi[i][0] && g[i][1] == sasiedzi[i][2]){
				if(uzyte[min(i, sasiedzi[i][1])] == 0){
					uzyte[min(i, sasiedzi[i][1])] = 1;
					answer(i, sasiedzi[i][1]);
				}
			}
			else if(g[i][0] == sasiedzi[i][1] && g[i][1] == sasiedzi[i][2]){
				if(uzyte[min(i, sasiedzi[i][0])] == 0){
					uzyte[min(i, sasiedzi[i][0])] = 1;
					answer(i, sasiedzi[i][0]);
				}
			}
		}
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36