Submission #552073

#	Time	Username	Problem	Language	Result	Execution time	Memory
552073		i_am_noob	Chameleon's Love (JOI20_chameleon)	C++17	24 / 100	64 ms	592 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
//#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

namespace {

const int maxn=505;

vector<int> adj[maxn*2];
bool vis[maxn*2];

mt19937 rng(49);

vector<int> gen(vector<int>& vec, int l, int r){
	vector<int> res;
	rep2(i,l,r+1) res.pb(vec[i]);
	return res;
}

int query(vector<int> vec){
	for(auto& i: vec) i++;
	return Query(vec);
}

bool good(vector<int> vec){
	return query(vec)==sz(vec);
}

}  // namespace

void Solve(signed n) {
	vector<int> ord;
	set<pii> st;
	rep1(_,20){
		ord.clear();
		rep(2*n) ord.pb(i);
		shuffle(all(ord),rng);
		vector<int> vec;
		memset(vis,0,sizeof vis);
		for(auto i: ord){
			bool flag=1;
			for(auto j: adj[i]) if(vis[j]) flag=0;
			if(!flag) continue;
			int l=0;
			flag=1;
			while(1){
				vector<int> tmp=gen(vec,l,sz(vec)-1);
				tmp.pb(i);
				if(good(tmp)) break;
				int r=sz(vec)-1;
				while(l<r){
					int mid=l+r>>1;
					tmp=gen(vec,l,mid);
					tmp.pb(i);
					if(good(tmp)) l=mid+1;
					else r=mid;
				}
				adj[vec[l]].pb(i),adj[i].pb(vec[l]);
				st.insert({min(i,vec[l]),max(i,vec[l])});
				l++;
				flag=0;
				if(l>=sz(vec)) break;
			}
			if(flag) vec.pb(i),vis[i]=1;
		}
	}
	for(auto [x,y]: st) bug(x,y);
	rep(2*n) bug(i,sz(adj[i]));
	rep(2*n) assert(sz(adj[i])==1||sz(adj[i])==3);
	rep(2*n) if(sz(adj[i])==3){
		if(query({i,adj[i][0],adj[i][1]})==1) st.erase({min(i,adj[i][2]),max(i,adj[i][2])}),bug(min(i,adj[i][2]),max(i,adj[i][2]));
		else if(query({i,adj[i][0],adj[i][2]})==1) st.erase({min(i,adj[i][1]),max(i,adj[i][1])}),bug(min(i,adj[i][1]),max(i,adj[i][1]));
		else st.erase({min(i,adj[i][0]),max(i,adj[i][0])}),bug(min(i,adj[i][0]),max(i,adj[i][0]));
	}
	//assert(sz(st)==n);
	for(auto [x,y]: st) Answer(x+1,y+1);
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |      int mid=l+r>>1;
      |              ~^~
chameleon.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define bug(...) 777771449
      |                  ^~~~~~~~~
chameleon.cpp:97:22: note: in expansion of macro 'bug'
   97 |  for(auto [x,y]: st) bug(x,y);
      |                      ^~~
chameleon.cpp:97:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   97 |  for(auto [x,y]: st) bug(x,y);
      |           ^~~~~
chameleon.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define bug(...) 777771449
      |                  ^~~~~~~~~
chameleon.cpp:98:11: note: in expansion of macro 'bug'
   98 |  rep(2*n) bug(i,sz(adj[i]));
      |           ^~~
chameleon.cpp:101:125: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |   if(query({i,adj[i][0],adj[i][1]})==1) st.erase({min(i,adj[i][2]),max(i,adj[i][2])}),bug(min(i,adj[i][2]),max(i,adj[i][2]));
      |                                                                                                                             ^
chameleon.cpp:102:130: warning: right operand of comma operator has no effect [-Wunused-value]
  102 |   else if(query({i,adj[i][0],adj[i][2]})==1) st.erase({min(i,adj[i][1]),max(i,adj[i][1])}),bug(min(i,adj[i][1]),max(i,adj[i][1]));
      |                                                                                                                                  ^
chameleon.cpp:103:92: warning: right operand of comma operator has no effect [-Wunused-value]
  103 |   else st.erase({min(i,adj[i][0]),max(i,adj[i][0])}),bug(min(i,adj[i][0]),max(i,adj[i][0]));
      |                                                                                            ^

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