제출 #423683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423683		oolimry	카멜레온의 사랑 (JOI20_chameleon)	C++17	40 / 100	32 ms	332 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

vector<int> adj[1005];
int likes[1005];
int answered[1005];

void addedge(int u, int v){
	//show2(u,v);
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void answer(int u, int v){
	//show3("ANS", u, v);
	if(answered[u] or answered[v]) return;
	answered[u] = 1;
	answered[v] = 1;
	Answer(u,v);
}

void Solve(int n){
	for(int i = 1;i <= 2*n;i++){
		for(int j = i+1;j <= 2*n;j++){
			int res = Query({i,j});
			if(res == 1) addedge(i,j);
		}
	}
	
	///the last stuff;
	for(int i = 1;i <= 2*n;i++){
		//if(answered[i]) continue;
		if(sz(adj[i]) == 1){
			answer(i, adj[i][0]);
			//show2(i, adj[i][0]);
		}
		else if(sz(adj[i]) == 3){
			vector<int> &v = adj[i];
			if(Query({i,v[0],v[1]}) == 1) likes[i] = v[2];
			if(Query({i,v[2],v[1]}) == 1) likes[i] = v[0];
			if(Query({i,v[0],v[2]}) == 1) likes[i] = v[1];
			//show2(i, likes[i]);
		}
		else assert(false);
	}
	
	for(int i = 1;i <= 2*n;i++){
		if(answered[i]) continue;
		for(int x : adj[i]){
			if(likes[x] != i and likes[i] != x) answer(i,x);
		}
	}
}	

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