Submission #937332

#	Time	Username	Problem	Language	Result	Execution time	Memory
937332		freedommo33	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	31 ms	844 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"
#include <vector>
#define query Query
#define answer Answer
constexpr long long M = 1005;
using namespace std;
vector<vector<int>> sasiedzi(M);
vector<vector<long long>> g(M);
vector<vector<long long>> g2(M);
long long syn[M];
bool uzyte[M];
long long kolor[M];
vector<long long> 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(long long p, long long k, long long numer, long long 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);	
}
long long numero;
long long bs(long long koniec){
	long long temp2 = ilews(1, spojna[0].size(), 0, koniec);
	long long numer = 0;
	long long temp = spojna[0].size();
	if(temp < temp2){
		numer = 1;
		temp2 = ilews(1, spojna[1].size(), 1, koniec);
		temp = spojna[1].size();
		if(temp < temp2 && numer==1) return -1;
	}
	long long 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(mid-p+1 < temp2) p = mid + 1;
		else	k = mid;
	}
	numero = numer;
	return p-1;
}
 
void Solve(int n) {
	for(int i=1; i<=2*n; i++){
		long long aktKolor = 1;
		long long wyn = bs(i);
		vector<long long> doDodania;
		while(wyn!=-1){
			sasiedzi[i].push_back(spojna[numero][wyn]);
			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);
		}
		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 i=1; i<=n*2; i++){
		sort(sasiedzi[i].begin(), sasiedzi[i].end());
		if(sasiedzi[i].size()!=1){
			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];
		}
	}
	for(long long 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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36