Submission #448802

#	Time	Username	Problem	Language	Result	Execution time	Memory
448802		kimjg1119	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	59 ms	4032 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

int N;
int color[1010], lk[1010][1010];
vector<int> adj[1010];

int send_query(int t1, int t2, int t3){
	vector<int> tmp;
	tmp.push_back(t1);
	tmp.push_back(t2);
	tmp.push_back(t3);
	return Query(tmp);
}

int vis[1010];
void recolor(int x){
	vis[x] = 1;
	color[x] = 3 - color[x];
	for(int th : adj[x])
		if(!vis[th]) recolor(th);
}

int info(int h, vector<int> &a){
	// check there is an information
	a.push_back(h);
	if(Query(a) == a.size()){
		a.pop_back();
		return -1;
	}
	a.pop_back();
	
	// binary search
	int left = a.size();
	vector<int> chk(left);
	while(left >= 2){
		int mid = left / 2;
		vector<int> v;
		for(int i = 0; i < a.size(); i++){
			if(!chk[i]) v.push_back(a[i]);
			if(v.size() == mid) break;
		}
		
		v.push_back(h);
		int ret = Query(v);
		
		if(ret < mid + 1){
			int cnt = 0;
			for(int i = 0; i < a.size(); i++){
				if(chk[i]) continue;
				if(cnt < mid) cnt++;
				else chk[i] = 1;
			}
			left = mid;
		}
		else{
			int cnt = 0;
			for(int i = 0; i < a.size(); i++){
				if(chk[i]) continue;
				cnt++;
				chk[i] = 1;
				if(cnt == mid) break;
			}
			left = left - mid;
		}
	}
	
	for(int i = 0; i < a.size(); i++){
		if(!chk[i]){
			int ret = a[i];
			/*cout << "A";
			fflush(stdout);*/
			a.erase(a.begin() + i);
			/*cout << "B";
			fflush(stdout);*/
			return ret;
		}
	}
	return -1;
}

int ans_chk[1010];
void find_like(int x){
	if(adj[x].size() == 1){
		// 양방향에 대한 처리
		if(ans_chk[x] || ans_chk[adj[x].back()]) return;
		Answer(x, adj[x].back());
		ans_chk[x] = ans_chk[adj[x].back()] = 1;
	}
	else{
		assert(adj[x].size() == 3);
		
		int t1 = adj[x][0], t2 = adj[x][1], t3 = adj[x][2];
		int r1 = send_query(x, t1, t2);
		int r2 = send_query(x, t2, t3);
		int r3 = send_query(x, t3, t1);
		
		if(r1 == 1) lk[x][t3] = 1;
		else if(r2 == 1) lk[x][t1] = 1;
		else if(r3 == 1) lk[x][t2] = 1;
	}
}

void Solve(int n){
	N = n * 2;
	
	for(int i = 1; i <= N; i++){
		vector<int> a, b;
		if(!color[i]) color[i] = 1;
		for(int j = 1; j < i; j++)
			if(color[j] == 1) a.push_back(j);
			else if(color[j] == 2) b.push_back(j);
		vector<int> ta, tb;
		while(true){
			int ret = info(i, a);
			if(ret == -1) break;
			ta.push_back(ret);
		}
		while(true){
			int ret = info(i, b);
			if(ret == -1) break;
			tb.push_back(ret);
		}
		
		for(int h : ta){
			if(color[h] == color[i]){
				memset(vis, 0, sizeof(vis));
				recolor(h);
			}
			adj[i].push_back(h);
			adj[h].push_back(i);
		}
		for(int h : tb){
			if(color[h] == color[i]){
				memset(vis, 0, sizeof(vis));
				recolor(h);
			}
			adj[i].push_back(h);
			adj[h].push_back(i);
		}
	}
	
	for(int i=1;i<=N;i++)
		find_like(i);
	
	for(int i = 1; i <= N; i++){
		if(ans_chk[i]) continue;
		for(auto h : adj[i]){
			if(!lk[h][i] && !lk[i][h]){
				Answer(h, i);
				ans_chk[h] = ans_chk[i] = 1;
			}
		}
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'int info(int, std::vector<int>&)':
chameleon.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if(Query(a) == a.size()){
      |     ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
chameleon.cpp:43:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |    if(v.size() == mid) break;
      |       ~~~~~~~~~^~~~~~
chameleon.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int i = 0; i < a.size(); i++){
      |                   ~~^~~~~~~~~~
chameleon.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for(int i = 0; i < a.size(); i++){
      |                   ~~^~~~~~~~~~
chameleon.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < a.size(); i++){
      |                 ~~^~~~~~~~~~

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