Submission #1171155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171155		henriess	Chameleon's Love (JOI20_chameleon)	C++20	0 / 100	0 ms	416 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
void Solve(int N) {
	//if N is less than 7
	//I can brute force 
	//N <= 7, that means 
	//I can hold a meeting of 2 chameleons 
	//if 1 chameleons likes the other chameleon and the other chameleon does not, there will be 1 distinct color 
	//if both chameleons like each other, there will be 2 distinct colors 
	
	
	//St 1 : both chameleons like each other 
	//when both chameleons like each other, the number of distinct colors will not change 
	//only case when there is lower distinct colors than number of chameleons is when 2 chameleons are of the same color 
	
	vector<long long> colors;
	for(int i = 1;i<=2*N;i++){
		colors.push_back(i);
	}
	vector<pair<long long,long long>> ans;
	while (!colors.empty()){
		long long current = colors[0];
		//binary search to find the chameleon with the same color as current 
		long long lb = 0;
		long long ub = colors.size()-1;
		while (lb < ub){
			long long mid = (lb + ub) / 2;
			vector<int> temp1;
			vector<int> temp2; 
			for(int i = 0;i<=mid;i++){
				temp1.push_back(colors[i]);
			}
			for(int i = 1;i<=mid;i++){
				temp2.push_back(colors[i]);
			}
			int x = Query(temp1);
			int y = Query(temp2);
			if (x == y){
				ub = mid;
			}
			else{
				lb = mid + 1;
			}
		}
		ans.push_back({colors[lb], colors[0]});
		colors.erase(colors.begin());
		colors.erase(colors.begin() + lb);
	}
	for(int i = 0;i<ans.size();i++){
		Answer(ans[i].first,ans[i].second);
	}
		
}

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