제출 #487930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487930		i_am_noob	Minerals (JOI19_minerals)	C++17	100 / 100	241 ms	10516 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],p[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);
	int dp[50005];
	dp[0]=inf;
	dp[1]=0;
	dp[2]=2;
	p[2]=1;
	rep2(i,3,43005){
		dp[i]=inf;
		rep2(j,i/5,i*2/5+1){
			int k=dp[j]+dp[i-j]+j+i-1;
			if(k<dp[i]) dp[i]=k,p[i]=j;
		}
	}
	assert(dp[43000]+2*43000==999976);
	rep1(_,49){
		if(sz(vec)==n) break;
		int cur=0;
		vector<int> vec1;
		for(auto& vv: vec){
			if(sz(vv)==1){
				cur++;
				continue;
			} 
			int s;
			if(a[1][cur]) s=sz(vv)-p[sz(vv)];
			else s=p[sz(vv)];
			bug(sz(vv),s);
			vec1.pb(s);
			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);
		}
		reverse(all(vec1));
		assert(cur==n);
		vector<vector<int>> nvec;
		for(auto& vv: vec){
			if(sz(vv)==1){
				nvec.pb(vv);
				continue;
			}
			int s=vec1.back();
			vec1.pop_back();
			bool good[sz(vv)];
			memset(good,0,sizeof good);
			nvec.pb({});
			int goodcnt=0,badcnt=0;
			rep(sz(vv)){
				if(goodcnt==s) good[i]=0;
				else if(badcnt==sz(vv)-s) good[i]=1;
				else good[i]=query(0,vv[i]);
				if(good[i]) goodcnt++;
				else badcnt++;
			}
			rep(sz(vv)) if(good[i]) nvec.back().pb(vv[i]);
			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]]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define bug(...) 826
      |                  ^~~
minerals.cpp:89:4: note: in expansion of macro 'bug'
   89 |    bug(sz(vv),s);
      |    ^~~

• 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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10