oj.uz

Submission #935276

# Submission time Handle Problem Language Result Execution time Memory
935276 2024-02-29T02:55:04 Z freedommo33 Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 30 ms 808 KB 
#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;
	//for(auto i:v) cout<<i<<",";
	//cout<<"->"<<query(v)<<endl;
	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);
	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);
		//cout<<"S0: ";
		//for(auto i:spojna[0]) cout<<i<<" ";
		//cout<<endl;
		//cout<<p<<" "<<mid<<"X"<<temp1<<" "<<temp2<<endl;
		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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 26 ms 540 KB Output is correct
4 Correct 26 ms 596 KB Output is correct
5 Correct 26 ms 344 KB Output is correct
6 Correct 26 ms 596 KB Output is correct
7 Correct 28 ms 808 KB Output is correct
8 Correct 26 ms 540 KB Output is correct
9 Correct 26 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 500 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 500 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 532 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 30 ms 344 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 26 ms 540 KB Output is correct
4 Correct 26 ms 596 KB Output is correct
5 Correct 26 ms 344 KB Output is correct
6 Correct 26 ms 596 KB Output is correct
7 Correct 28 ms 808 KB Output is correct
8 Correct 26 ms 540 KB Output is correct
9 Correct 26 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 500 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 532 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Incorrect 30 ms 344 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -