Submission #1130564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130564		vako_p	카멜레온의 사랑 (JOI20_chameleon)	C++20	0 / 100	29 ms	492 KiB

chameleon

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#include "chameleon.h"

ll n;
vector<ll> v[4],vv[4],q,a[2005];
bool vis[2005];

ll Queryy(const vector<ll> &p){
//	for(auto it : p) if(it < 1 or it > 2 * n) assert(0);
	return Query(p);
}

void query(ll i, ll l, ll r){
	for(int j = l; j <= r; j++) q.pb(v[i][j]);
}

ll bins(ll i, ll j, ll i1, ll l, ll r){
	q.clear();
	q.pb(v[i][j]);
	query(i1, l, r);
	if(Queryy(q) == q.size()) return -1;
	l--;
	while(r > l + 1){
		ll mid = l + (r - l) / 2;
		q.clear();
		q.pb(v[i][j]);
		query(i1, l + 1, mid);
		if(Queryy(q) == q.size()) l = mid;
		else r = mid;
	}
	return r;
}

void Solve(int N) {
	n = N;
	for(int i = 1; i <= 2 * n; i++){
		vv[0].pb(i);
	}
	for(int i = 0; i < 3; i++){
		if(vv[i].size() == 0) break;
		v[i].pb(vv[i][0]);
		for(int j = 1; j < vv[i].size(); j++){
			v[i].pb(vv[i][j]);
			if(Queryy(v[i]) != v[i].size()){
				vv[i + 1].pb(vv[i][j]);
				v[i].pop_back();
			}
		}
	}
	
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < v[i].size(); j++){
			for(int k = i; k < 4; k++){
				for(int j1 = 0; j1 < v[k].size(); j1++){
					if(k != i or j1 != j)if(Queryy({v[i][j], v[k][j1]}) == 1){
						assert(k != i);
						a[v[i][j]].pb(v[k][j1]);
						a[v[k][j1]].pb(v[i][j]);
					}
				}
			}
		}
	}
	
//	for(int i = 1; i <= 2 * n; i++){
//		for(int j = i + 1; j <= 2 * n; j++){
//			if(Query({i, j}) == 1){
//				a[i].pb(j);
//				a[j].pb(i);
//			}
//		}
//	}
//	for(int i = 0; i < 3; i++){
//		for(int j = 0; j < v[i].size(); j++){
//			for(int k = i + 1; k < 4; k++){
//				ll l = 0,sz = v[k].size(), r = sz - 1;
//				while(true){
//					l = bins(i, j, k, l, r);
//					if(l == -1) break;
//					a[v[k][l]].pb(v[i][j]);
//					a[v[i][j]].pb(v[k][l++]);
//				}
//			}
//		}
//	}
	
	for(int i = 1; i <= 2 * n; i++){
		if(vis[i]) continue;
		vis[i] = true;
		if(a[i].size() == 1){
			vis[a[i][0]] = true;
			Answer(i, a[i][0]);
			continue;
		}
//		assert(a[i].size() == 3);
		ll x = a[i][0], y = a[i][1], z = a[i][2];
		if(Queryy({i, x, y}) == 1) a[i].pop_back();
		else if(Queryy({i, x, z}) == 1) a[i].erase(a[i].begin() + 1);
		else a[i].erase(a[i].begin());
		if(vis[a[i][0]]){
			vis[a[i][1]] = true;
			Answer(i, a[i][1]);
			continue;
		}
		bool ok = (a[a[i][0]].size() > 1);
		for(auto it : a[a[i][0]]){
			if(it == i) continue;
			if(Queryy({i, a[i][0], it}) == 1){
				ok = false;
				break;
			}
		}
		if(ok){
			vis[a[i][1]] = true; 
			Answer(i, a[i][1]);
		}
		else{
			vis[a[i][0]] = true;
			Answer(i, a[i][0]);
		}
	}
}

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