Submission #212032

#	Time	Username	Problem	Language	Result	Execution time	Memory
212032		ryansee	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	87 ms	632 KiB

chameleon

#include "chameleon.h"
#include "bits/stdc++.h"
using namespace std;
namespace {

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef int ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (1006)
vector<int> v[MAXN];
int colour[MAXN], out[MAXN], in[MAXN];
bitset<MAXN> match;
}  // namespace

void Solve(int n) {
	vector<vector<int>> C(2, vector<int>());
	auto get_from=[&](ll b,ll s,ll e){
		vector<int> res;
		FOR(i,s,e) res.pb(C[b][i]);
		return res;
	};
	auto concat=[&](vector<int> v, int x){
		v.pb(x);
		return v;
	};
	ll ls_0=0, ls_1=0;
	auto get_sz=[&](ll b){
		return siz(C[b]) - (b?ls_1:ls_0);
	};
	auto add_edge=[&](ll a,ll b){ return v[a].eb(b), v[b].eb(a); };
	auto solve=[&](ll b,ll x){
		ll st=(b?ls_1:ls_0)-1, en=siz(C[b]);
		// minimum pos such that become <= same
		while(en-st>1){
			ll mid=(st+en)>>1;
			if(Query(concat(get_from(b,(b?ls_1:ls_0),mid),x))<=mid-(b?ls_1:ls_0)+1) en=mid;
			else st=mid;
		}
		assert(en^siz(C[b]));
		add_edge(x, C[b][en]);
		return en;
	};
	n*=2;
	FOR(i,1,n){
		ls_0=ls_1=0;
		FOR(ii,1,3){
			ll a=Query(concat(get_from(0,ls_0,siz(C[0])-1), i)),b=Query(concat(get_from(1,ls_1,siz(C[1])-1), i));
			if(a > get_sz(0) && b > get_sz(1)) break;
			if(a<=get_sz(0)){
				ls_0=solve(0,i)+1;
			}else if(b<=get_sz(1)){
				ls_1=solve(1,i)+1;
			}
		}
		mmst(colour,-1), C[0].clear(), C[1].clear();
		function<void(ll)>dfs=[&](ll x){
			for(auto i:v[x]) if(colour[i]==-1){
				colour[i]=colour[x]^1;
				dfs(i);
			}else assert(colour[i]==!colour[x]);
		};
		FOR(j,1,i)if(colour[j]==-1){
			colour[j]=0, dfs(j);
		}
		FOR(j,1,i) C[colour[j]].pb(j);
	}
	assert(C[0].size()==n/2&&C[1].size()==n/2);
	FOR(i,1,n){
		if(v[i].size()==1){
			if(match[i])continue;
			match[i]=match[v[i][0]]=1;
			Answer(i, v[i][0]);
		}else{
			assert(v[i].size()==3);
			ll a=v[i][0], b=v[i][1], c=v[i][2];
			ll ab=Query(vector<ll>()={a,b,i});
			ll ac=Query(vector<ll>()={a,c,i});
			ll bc=Query(vector<ll>()={b,c,i});
			if(ab==1) { // c is x's out
				out[i]=c, in[c]=i;
			}else if(ac==1) { // is b
				out[i]=b, in[b]=i;
			}else if(bc==1) { // is a
				out[i]=a, in[a]=i;
			}else assert(0);
		}
	}
	FOR(i,1,n)if(match[i]==0){
		v[i].erase(find(all(v[i]), out[i]));
		v[i].erase(find(all(v[i]), in[i]));
		assert(v[i].size()==1);
		match[i]=match[v[i][0]]=1;
		Answer(i, v[i][0]);
	}
	return;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from chameleon.cpp:2:
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(C[0].size()==n/2&&C[1].size()==n/2);
         ~~~~~~~~~~~^~~~~
chameleon.cpp:89:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(C[0].size()==n/2&&C[1].size()==n/2);
                           ~~~~~~~~~~~^~~~~

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