Submission #487917

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
487917	2021-11-17T04:23:39 Z	i_am_noob	Minerals (JOI19_minerals)	C++17	90 / 100	71 ms	8248 KB

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);
	mt19937 rng(7777714);
	shuffle(all(vec.back()),rng);
	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)+1)/2;
			else s=sz(vv)/2;
			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]]);
	}
}

Subtask #1
6.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	328 KB	Output is correct
2	Correct	328 KB	Output is correct
3	Correct	328 KB	Output is correct
4	Correct	328 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	456 KB	Output is correct
2	Correct	2 ms	584 KB	Output is correct
3	Correct	5 ms	968 KB	Output is correct
4	Correct	9 ms	1608 KB	Output is correct
5	Correct	17 ms	2944 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct

Subtask #4
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct
15	Correct	56 ms	7568 KB	Output is correct
16	Correct	56 ms	7536 KB	Output is correct
17	Correct	47 ms	7636 KB	Output is correct
18	Correct	55 ms	7484 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct
15	Correct	56 ms	7568 KB	Output is correct
16	Correct	56 ms	7536 KB	Output is correct
17	Correct	47 ms	7636 KB	Output is correct
18	Correct	55 ms	7484 KB	Output is correct
19	Correct	58 ms	7752 KB	Output is correct
20	Correct	63 ms	7716 KB	Output is correct
21	Correct	60 ms	7732 KB	Output is correct
22	Correct	46 ms	7556 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct
15	Correct	56 ms	7568 KB	Output is correct
16	Correct	56 ms	7536 KB	Output is correct
17	Correct	47 ms	7636 KB	Output is correct
18	Correct	55 ms	7484 KB	Output is correct
19	Correct	58 ms	7752 KB	Output is correct
20	Correct	63 ms	7716 KB	Output is correct
21	Correct	60 ms	7732 KB	Output is correct
22	Correct	46 ms	7556 KB	Output is correct
23	Correct	58 ms	7800 KB	Output is correct
24	Correct	57 ms	7836 KB	Output is correct
25	Correct	62 ms	7812 KB	Output is correct
26	Correct	48 ms	7696 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct
15	Correct	56 ms	7568 KB	Output is correct
16	Correct	56 ms	7536 KB	Output is correct
17	Correct	47 ms	7636 KB	Output is correct
18	Correct	55 ms	7484 KB	Output is correct
19	Correct	58 ms	7752 KB	Output is correct
20	Correct	63 ms	7716 KB	Output is correct
21	Correct	60 ms	7732 KB	Output is correct
22	Correct	46 ms	7556 KB	Output is correct
23	Correct	58 ms	7800 KB	Output is correct
24	Correct	57 ms	7836 KB	Output is correct
25	Correct	62 ms	7812 KB	Output is correct
26	Correct	48 ms	7696 KB	Output is correct
27	Correct	63 ms	8096 KB	Output is correct
28	Correct	71 ms	8192 KB	Output is correct
29	Correct	56 ms	8004 KB	Output is correct
30	Correct	48 ms	7876 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct
15	Correct	56 ms	7568 KB	Output is correct
16	Correct	56 ms	7536 KB	Output is correct
17	Correct	47 ms	7636 KB	Output is correct
18	Correct	55 ms	7484 KB	Output is correct
19	Correct	58 ms	7752 KB	Output is correct
20	Correct	63 ms	7716 KB	Output is correct
21	Correct	60 ms	7732 KB	Output is correct
22	Correct	46 ms	7556 KB	Output is correct
23	Correct	58 ms	7800 KB	Output is correct
24	Correct	57 ms	7836 KB	Output is correct
25	Correct	62 ms	7812 KB	Output is correct
26	Correct	48 ms	7696 KB	Output is correct
27	Correct	63 ms	8096 KB	Output is correct
28	Correct	71 ms	8192 KB	Output is correct
29	Correct	56 ms	8004 KB	Output is correct
30	Correct	48 ms	7876 KB	Output is correct
31	Correct	62 ms	8188 KB	Output is correct
32	Correct	67 ms	8148 KB	Output is correct
33	Correct	59 ms	8248 KB	Output is correct
34	Correct	49 ms	7968 KB	Output is correct

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	5 ms	968 KB	Output is correct
8	Correct	9 ms	1608 KB	Output is correct
9	Correct	17 ms	2944 KB	Output is correct
10	Correct	1 ms	456 KB	Output is correct
11	Correct	13 ms	2164 KB	Output is correct
12	Correct	19 ms	2976 KB	Output is correct
13	Correct	18 ms	2976 KB	Output is correct
14	Correct	21 ms	2948 KB	Output is correct
15	Correct	56 ms	7568 KB	Output is correct
16	Correct	56 ms	7536 KB	Output is correct
17	Correct	47 ms	7636 KB	Output is correct
18	Correct	55 ms	7484 KB	Output is correct
19	Correct	58 ms	7752 KB	Output is correct
20	Correct	63 ms	7716 KB	Output is correct
21	Correct	60 ms	7732 KB	Output is correct
22	Correct	46 ms	7556 KB	Output is correct
23	Correct	58 ms	7800 KB	Output is correct
24	Correct	57 ms	7836 KB	Output is correct
25	Correct	62 ms	7812 KB	Output is correct
26	Correct	48 ms	7696 KB	Output is correct
27	Correct	63 ms	8096 KB	Output is correct
28	Correct	71 ms	8192 KB	Output is correct
29	Correct	56 ms	8004 KB	Output is correct
30	Correct	48 ms	7876 KB	Output is correct
31	Correct	62 ms	8188 KB	Output is correct
32	Correct	67 ms	8148 KB	Output is correct
33	Correct	59 ms	8248 KB	Output is correct
34	Correct	49 ms	7968 KB	Output is correct
35	Incorrect	58 ms	6316 KB	Wrong Answer [2]
36	Halted	0 ms	0 KB	-

Submission #487917

Compilation message