Submission #487914

#	Time	Username	Problem	Language	Result	Execution time	Memory
487914		i_am_noob	Minerals (JOI19_minerals)	C++17	80 / 100	49 ms	7364 KiB

minerals

#include "minerals.h"

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

#define ll long long
//#define int ll
#define ull unsigned long long
#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 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))
#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(...) 826
#endif

const int maxn=43005;

int x,out_id[2][maxn];
bool a[2][maxn];

inline bool query(int id1, int id2){
	int y=Query(out_id[id1][id2]);
	a[id1][id2]^=1;
	bool flag=x!=y;
	x=y;
	return flag;
}

void Solve(int n){
	x=0;
	int cur1=0,cur2=0;
	rep(2*n){
		int y=Query(i+1);
		if(y>x){
			out_id[0][cur1++]=i+1;
		}
		else{
			out_id[1][cur2++]=i+1;
		}
		x=y;
	}
	assert(cur1==n&&cur2==n);
	rep(n) a[0][i]=1;
	vector<vector<int>> vec;
	vec.pb({});
	rep(n) vec.back().pb(i);
	rep1(_,16){
		if(sz(vec)==n) break;
		int cur=0;
		for(auto& vv: vec){
			if(sz(vv)==1){
				cur++;
				continue;
			}
			int s=pow2(__lg(sz(vv)-1));
			rep(sz(vv)){
				if(i<s&&!a[1][cur+i]) query(1,cur+i);
				if(i>=s&&a[1][cur+i]) query(1,cur+i);
			}
			cur+=sz(vv);
		}
		assert(cur==n);
		vector<vector<int>> nvec;
		for(auto& vv: vec){
			if(sz(vv)==1){
				nvec.pb(vv);
				continue;
			}
			int s=pow2(__lg(sz(vv)-1));
			bool good[sz(vv)];
			memset(good,0,sizeof good);
			nvec.pb({});
			rep(sz(vv)-1){
				good[i]=query(0,vv[i]);
				if(good[i]) nvec.back().pb(vv[i]);
			}
			if(count(good,good+sz(vv),1)!=s){
				good[sz(vv)-1]=1;
				nvec.back().pb(vv.back());
			}
			assert(sz(nvec.back())==s);
			nvec.pb({});
			rep(sz(vv)) if(!good[i]) nvec.back().pb(vv[i]);
			assert(sz(nvec.back())==sz(vv)-s);
		}
		vec=nvec;
	}
	assert(sz(vec)==n);
	rep(n){
		Answer(out_id[1][i],out_id[0][vec[i][0]]);
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10