Submission #212247

#	Time	Username	Problem	Language	Result	Execution time	Memory
212247		abacaba	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	67 ms	508 KiB

chameleon

#include <chameleon.h>
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
constexpr int Q_MAX = 20'000;
constexpr int N_MAX = 515;
int n, cl[N_MAX << 1];
 
vector <int> g[N_MAX << 1];
vector <int> s[2];
 
void dfs(int v) {
	for(int to : g[v])
		if(!cl[to]) {
			cl[to] = 3 - cl[v];
			dfs(to);
		}
}
 
 
inline bool bad(vector <int> x, int r) {
	x.pb(r);
	return Query(x) != x.size();
}
 
int same_color[N_MAX << 1];
 
inline pii gt(int a, int b) {
	return mp(min(a, b), max(a, b));
}
 
set <pii> is;
 
int loves[N_MAX << 1];
 
void Solve(int N) {
	n = N;
	for(int i = 1; i <= 2 * n; ++i) {
		for(int j = 0; j < 2; ++j)
			s[j].clear();
		for(int j = 1; j < i; ++j)
			cl[j] = 0;
		for(int j = 1; j < i; ++j) {
			if(!cl[j]) {
				cl[j] = 1;
				dfs(j);
			}
			s[cl[j] - 1].pb(j);
		}
		for(int j = 0; j < 2; ++j) {
			vector <int> cur = s[j];
			while(bad(cur, i)) {
				int l = 0, r = (int)cur.size() - 1, res = -1;
				while(l <= r) {
					int mid = l + r >> 1;
					if(bad(vector <int> (cur.begin() + mid, cur.end()), i))
						l = mid + 1, res = mid;
					else
						r = mid - 1;
				}
				assert(res != -1);
				g[cur[res]].pb(i), g[i].pb(cur[res]);
				cur = vector <int> (cur.begin(), cur.begin() + res);
			}
		}
	}
	for(int i = 1; i <= 2 * n; ++i) {
		assert(g[i].size() == 1 || g[i].size() == 3);
		if(g[i].size() == 1)
			same_color[i] = g[i][0];
		else {
			for(int mask = 0; mask < 8; ++mask) {
				if(cntbit(mask) != 2)
					continue;
				vector <int> now = {i};
				for(int j = 0; j < 3; ++j)
					if(1 << j & mask)
						now.pb(g[i][j]);
				if(Query(now) == 1) {
					for(int j = 0; j < 3; ++j)
						if(!(1 << j & mask))
							loves[i] = g[i][j];
				}
			}
		}
	}
	for(int i = 1; i <= 2 * n; ++i) {
		if(g[i].size() == 1)
			is.insert(gt(i, same_color[i]));
		else {
			for(int j = 0; j < 3; ++j) {
				if(g[i][j] != loves[i] && loves[g[i][j]] != i) {
					same_color[g[i][j]] = i;
					same_color[i] = g[i][j];
				}
			}
		}
		is.insert(gt(same_color[i], i));
	}
	for(pii e : is)
		Answer(e.f, e.se);
}

Compilation message (stderr)

chameleon.cpp: In function 'bool bad(std::vector<int>, int)':
chameleon.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return Query(x) != x.size();
         ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:90:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int mid = l + r >> 1;
                ~~^~~

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