oj.uz

Submission #487928

# Submission time Handle Problem Language Result Execution time Memory
487928 2021-11-17T06:35:57 Z i_am_noob Minerals (JOI19_minerals) C++17
6 / 100
 191 ms 3056 KB 
#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(_,16){
		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]]);
	}
}

Compilation message

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 808 KB Output is correct
2 Correct 171 ms 1088 KB Output is correct
3 Runtime error 172 ms 3056 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 716 KB Output is correct
2 Correct 164 ms 564 KB Output is correct
3 Correct 180 ms 576 KB Output is correct
4 Correct 161 ms 704 KB Output is correct
5 Correct 191 ms 808 KB Output is correct
6 Correct 171 ms 1088 KB Output is correct
7 Runtime error 172 ms 3056 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -