Submission #550751

#	Time	Username	Problem	Language	Result	Execution time	Memory
550751		8e7	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	70 ms	1412 KiB

chameleon

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "chameleon.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
namespace {
	vector<int> ord, adj[maxn];
	bool vis[maxn];
	bool bad[maxn][maxn];
	void dfs(int n, int c, vector<int> &lef, vector<int> &rig) {
		vis[n] = 1;
		if (c) rig.push_back(n);
		else lef.push_back(n);
		for (int v:adj[n]) {
			if (!vis[v]) dfs(v, 1 - c, lef, rig); 
		}
	}
	int query(int x, vector<int> &v, int l, int r) { //[l, r)
		//debug(x, l, r);
		vector<int> vec;
		vec.push_back(ord[x]);
		for (int i = l;i < r;i++) vec.push_back(ord[v[i]]);
		if (r - l == 0) return 1;
		else return r - l + 1 - Query(vec);
	}
	void addedge(int x, vector<int> &v, int l) {
		if (l >= v.size() || !query(x, v, l, v.size())) return;
		int low = l, up = v.size();	
		while (low < up - 1) {
			int mid = (low + up) / 2;
			if (query(x, v, low, mid)) up = mid;
			else low = mid;
		}
		adj[x].push_back(v[low]);
		adj[v[low]].push_back(x);
		debug("edge", x, v[low]);
		addedge(x, v, low + 1);	
	}
}
void Solve(int N) {
	srand(time(NULL));
	vector<int> lef, rig;
	for (int i = 1;i <= 2 * N;i++) ord.push_back(i);	
	//random_shuffle(ord.begin(), ord.end());	
	ord.insert(ord.begin(), 0);
	//pary(ord.begin(), ord.end());
	for (int i = 2 * N;i > 0;i--) {
		random_shuffle(lef.begin(), lef.end());
		random_shuffle(rig.begin(), rig.end());
		addedge(i, lef, 0);
		addedge(i, rig, 0);
		for (int j = i;j <= 2 * N;j++) vis[j] = 0;		
		lef.clear(), rig.clear();
		for (int j = i;j <= 2 * N;j++) {
			if (!vis[j]) dfs(j, rand() % 2, lef, rig);
		}
		pary(lef.begin(), lef.end());
		pary(rig.begin(), rig.end());
		debug();
	}
	debug();
	auto getbad = [&](vector<int> &vec) {
		for (int i:vec) {
			if (adj[i].size() == 3) {
				vector<int> t1(1, ord[i]), t2(1, ord[i]);
				t1.push_back(ord[adj[i][0]]);
				t1.push_back(ord[adj[i][2]]);
				t2.push_back(ord[adj[i][0]]);
				t2.push_back(ord[adj[i][1]]);

				pary(t1.begin(), t1.end());
				pary(t2.begin(), t2.end());
				int val = 0;
				if (Query(t1) == 1) val = 1;
				else if (Query(t2) == 1) val = 2;
				bad[i][adj[i][val]] = bad[adj[i][val]][i] = 1;	
			}
		}
	};
	getbad(lef), getbad(rig);
	for (int i:lef) {
		debug(i);
		if (adj[i].size() == 1) debug(ord[i], ord[adj[i][0]]), Answer(ord[i], ord[adj[i][0]]);
		else {
			for (int v:adj[i]) {
				if (!bad[i][v]) debug(ord[i], ord[adj[i][0]]), Answer(ord[i], ord[v]);
			}
		}
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'void {anonymous}::addedge(int, std::vector<int>&, int)':
chameleon.cpp:44:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if (l >= v.size() || !query(x, v, l, v.size())) return;
      |       ~~^~~~~~~~~~~
chameleon.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
chameleon.cpp:53:3: note: in expansion of macro 'debug'
   53 |   debug("edge", x, v[low]);
      |   ^~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
chameleon.cpp:74:3: note: in expansion of macro 'pary'
   74 |   pary(lef.begin(), lef.end());
      |   ^~~~
chameleon.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
chameleon.cpp:75:3: note: in expansion of macro 'pary'
   75 |   pary(rig.begin(), rig.end());
      |   ^~~~
chameleon.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
chameleon.cpp:76:3: note: in expansion of macro 'debug'
   76 |   debug();
      |   ^~~~~
chameleon.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
chameleon.cpp:78:2: note: in expansion of macro 'debug'
   78 |  debug();
      |  ^~~~~
chameleon.cpp: In lambda function:
chameleon.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
chameleon.cpp:88:5: note: in expansion of macro 'pary'
   88 |     pary(t1.begin(), t1.end());
      |     ^~~~
chameleon.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
chameleon.cpp:89:5: note: in expansion of macro 'pary'
   89 |     pary(t2.begin(), t2.end());
      |     ^~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
chameleon.cpp:99:3: note: in expansion of macro 'debug'
   99 |   debug(i);
      |   ^~~~~
chameleon.cpp:14:20: warning: left operand of comma operator has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
chameleon.cpp:100:27: note: in expansion of macro 'debug'
  100 |   if (adj[i].size() == 1) debug(ord[i], ord[adj[i][0]]), Answer(ord[i], ord[adj[i][0]]);
      |                           ^~~~~
chameleon.cpp:14:20: warning: left operand of comma operator has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
chameleon.cpp:103:21: note: in expansion of macro 'debug'
  103 |     if (!bad[i][v]) debug(ord[i], ord[adj[i][0]]), Answer(ord[i], ord[v]);
      |                     ^~~~~

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