oj.uz

Submission #552101

# Submission time Handle Problem Language Result Execution time Memory
552101 2022-04-22T11:54:55 Z i_am_noob Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 34 ms 2888 KB 
#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],de[maxn*2][maxn*2],ready[maxn*2];
int used=0;

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){
	used++;
	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){
		int need=0;
		rep(2*n) rep1(j,i) if((!ready[i])&&(!ready[j])&&sz(adj[i])<3&&sz(adj[j])<3&&!de[i][j]) need++;
		if(need<=18000-used) break;
		ord.clear();
		rep(2*n){
			bool flag=0;
			rep1(j,2*n) if(i!=j&&!de[i][j]) flag=1;
			if(flag&&sz(adj[i])<3&&!ready[i]) 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;
			for(auto j: vec) de[i][j]=de[j][i]=1;
			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,ready[i]=1;
		}
	}
	rep(2*n) rep1(j,i) if((!ready[i])&&(!ready[j])&&sz(adj[i])<3&&sz(adj[j])<3&&!de[i][j]){
		if(query({i,j})==1){
			adj[i].pb(j),adj[j].pb(i);
			st.insert({min(i,j),max(i,j)});
		}
	}
	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

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:92:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |      int mid=l+r>>1;
      |              ~^~
chameleon.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define bug(...) 777771449
      |                  ^~~~~~~~~
chameleon.cpp:113:22: note: in expansion of macro 'bug'
  113 |  for(auto [x,y]: st) bug(x,y);
      |                      ^~~
chameleon.cpp:113:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  113 |  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:114:11: note: in expansion of macro 'bug'
  114 |  rep(2*n) bug(i,sz(adj[i]));
      |           ^~~
chameleon.cpp:117:125: warning: right operand of comma operator has no effect [-Wunused-value]
  117 |   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:118:130: warning: right operand of comma operator has no effect [-Wunused-value]
  118 |   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:119:92: warning: right operand of comma operator has no effect [-Wunused-value]
  119 |   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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 23 ms 1368 KB Output is correct
4 Correct 23 ms 1360 KB Output is correct
5 Correct 24 ms 1448 KB Output is correct
6 Correct 25 ms 1472 KB Output is correct
7 Correct 22 ms 1384 KB Output is correct
8 Correct 22 ms 1452 KB Output is correct
9 Correct 23 ms 1484 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Runtime error 34 ms 2888 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 23 ms 1368 KB Output is correct
4 Correct 23 ms 1360 KB Output is correct
5 Correct 24 ms 1448 KB Output is correct
6 Correct 25 ms 1472 KB Output is correct
7 Correct 22 ms 1384 KB Output is correct
8 Correct 22 ms 1452 KB Output is correct
9 Correct 23 ms 1484 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 0 ms 336 KB Output is correct
29 Correct 0 ms 336 KB Output is correct
30 Runtime error 34 ms 2888 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -