Submission #671966

#	Time	Username	Problem	Language	Result	Execution time	Memory
671966		ymm	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	50 ms	832 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace {

const int maxn = 1024;

vector<int> A[maxn];

int query(vector<int> vec)
{
	for (int &x : vec)
		x += 1;
	return Query(vec);
}

bool bin_query(int v, vector<int> vec, int l, int r)
{
	vector<int> dard = vector<int>(&vec[l], &vec[r]); // UB but whatever
	dard.push_back(v);
	return query(dard) != dard.size();
}

int bin(int v, vector<int> vec)
{
	int l = 0, r = vec.size();
	if (l == r)
		return -1;
	if (!bin_query(v, vec, l, r))
		return -1;
	while (r - l > 1) {
		int m = (l + r)/2;
		if (!bin_query(v, vec, l, m))
			l = m;
		else
			r = m;
	}
	return l;
}


bool vis[maxn];
void dfs(int v, int col, vector<int> vec[2])
{
	vis[v] = 1;
	vec[col].push_back(v);
	for (int u : A[v]) {
		if (!vis[u])
			dfs(u, 1-col, vec);
	}
}

void solve(int v)
{
	if (v == 0)
		return;
	solve(v-1);
	memset(vis, 0, v);
	vector<int> vec[2];
	Loop (u,0,v) {
		if (vis[u])
			continue;
		dfs(u, 0, vec);
	}
	Loop (col, 0, 2) {
		int i;
		while ((i = bin(v, vec[col])) != -1) {
			int u = vec[col][i];
			swap(vec[col][i], vec[col].back());
			vec[col].pop_back();
			A[v].push_back(u);
			A[u].push_back(v);
		}
	}
}

int love[maxn];
int match[maxn];

}  // namespace

void Solve(int N)
{
	solve(2*N-1);
	//Loop (i,0,2*N) {
	//	cerr << i << ": ";
	//	for (int j : A[i])
	//		cerr << j << ' ';
	//	cerr << '\n';
	//}
	memset(love, -1, sizeof(love));
	Loop (v,0,2*N) {
		if (A[v].size() == 1)
			continue;
		assert(A[v].size() == 3);
		int a = A[v][0];
		int b = A[v][1];
		int c = A[v][2];
		//cerr << v << ": " << v << ' ' << a << ' ' << b << ' ' << c << " - " << query({v, a, c}) << '\n';
		if (query({v, a, b}) == 1)
			love[v] = c;
		else if (query({v, a, c}) == 1)
			love[v] = b;
		else
			love[v] = a;
	}
	//Loop (i,0,2*N)
	//	cerr << love[i]+1 << ' ';
	//cerr << '\n';
	Loop (v,0,2*N) {
		if (A[v].size() == 1) {
			match[v] = A[v][0];
			continue;
		}
		int a = A[v][0];
		int b = A[v][1];
		int c = A[v][2];
		if (love[a] != v && love[v] != a)
			match[v] = a;
		else if (love[b] != v && love[v] != b)
			match[v] = b;
		else
			match[v] = c;
	}
	//Loop (i,0,2*N)
	//	cerr << match[i] << ' ';
	//cerr << '\n';
	Loop (i,0,2*N) {
		if (i > match[i])
			continue;
		Answer(i+1, match[i]+1);
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'bool {anonymous}::bin_query(int, std::vector<int>, int, int)':
chameleon.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  return query(dard) != dard.size();
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:106:14: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  106 |   if (query({v, a, b}) == 1)
      |              ^
chameleon.cpp:106:14: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
chameleon.cpp:108:19: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  108 |   else if (query({v, a, c}) == 1)
      |                   ^
chameleon.cpp:108:19: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]

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