Submission #581997

#	Time	Username	Problem	Language	Result	Execution time	Memory
581997		sysia	Chameleon's Love (JOI20_chameleon)	C++17	40 / 100	18 ms	336 KiB

chameleon

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "chameleon.h"
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


void Solve(int n){
	vector<vector<int>>diff(2*n+1);
	for (int i = 1; i<=2*n; i++){
		for (int j = 1; j<=2*n; j++){
			if (i == j) continue;
			int x = Query({i, j});
			if (x == 1)	diff[i].emplace_back(j);
		}
	}
	vector<pair<int, int>>ans;
	vector<int>G(2*n+1, -1), who(2*n+1, -1);
	// debug(diff);
	vector<bool>vis(2*n+1, 0);
	for (int i = 1; i<=2*n; i++){
		if ((int)diff[i].size() == 1 && !vis[diff[i][0]]){
			ans.emplace_back(i, diff[i][0]);
			vis[i] = 1;
			vis[diff[i][0]] = 1;
		} else if (diff[i].size() == 3) {
			vector<int>curr;
			for (int j = 0; j<3; j++){
				curr.clear();
				for (int k = 0; k<3; k++){
					if (k == j) continue;
					curr.emplace_back(diff[i][k]);
				}
				curr.emplace_back(i);
				if (Query(curr) == 1){
					G[i] = diff[i][j];
					who[diff[i][j]] = i;
				}
			}
			
		}
	}
	// debug(ans);
	// debug(G);
	// debug(who);
	for (int i = 1; i<=2*n; i++){
		if (vis[i]) continue;
		if ((int)diff[i].size() == 3){
			for (int j = 0; j<3; j++){
				if (diff[i][j] == G[i] || diff[i][j] == who[i]){
					continue;
				}
				ans.emplace_back(i, diff[i][j]);
				vis[i] = 1;
				vis[diff[i][j]] = 1;
			}
		}
	}
	// debug(ans);
	for (auto [a, b]:ans) Answer(a, b);
}

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