Submission #448726

#	Time	Username	Problem	Language	Result	Execution time	Memory
448726		kimjg1119	Chameleon's Love (JOI20_chameleon)	C++17	40 / 100	23 ms	328 KiB

chameleon

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

using namespace std;

int N;
int a[101][101], lk[101][101], chk[101];
vector<int> one[101];

int f(int t1, int t2){
	if(t1 == t2) exit(-1);
	if(t1 > t2) swap(t1, t2);
	return a[t1][t2];
}

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);
}

void find_like(int x){
	for(int i = 1; i <= N * 2; i++){
		if(i == x) continue;
		if(f(x, i) == 1) one[x].push_back(i);
	}
	if(one[x].size() == 1){
		// 양방향에 대한 처리
		if(chk[x] || chk[one[x].back()]) return;
		Answer(x, one[x].back());
		chk[x] = chk[one[x].back()] = 1;
	}
	else{
		assert(one[x].size() == 3);
		
		int t1 = one[x][0], t2 = one[x][1], t3 = one[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;
	for(int i = 1; i <= N * 2; i++)
		for(int j = i + 1; j <= N * 2; j++){
			vector<int> v;
			v.push_back(i);
			v.push_back(j);
			a[i][j] = Query(v);
		}
	
	for(int i = 1; i <= N * 2; i++)
		find_like(i);
	
	for(int i = 1; i <= N * 2; i++){
		if(chk[i]) continue;
		for(auto h : one[i]){
			if(!lk[h][i] && !lk[i][h]){
				Answer(h, i);
				chk[h] = chk[i] = 1;
			}
		}
	}
}

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