Submission #250193

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250193	2020-07-17T06:26:22 Z	errorgorn	Minerals (JOI19_minerals)	C++14	40 / 100	78 ms	3788 KB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
 
#define rep(x,s,e) for (auto x=s;x<e;x++)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int curr=0;
void rec(vector<int> v1,vector<int> v2,bool flag){
	/*
	for (auto &it:v1) cout<<it<<" ";cout<<endl;
	for (auto &it:v2) cout<<it<<" ";cout<<endl;
	cout<<endl;
	//*/
	
	if (sz(v1)==1){
		Answer(v1[0],v2[0]);
		
		curr=Query(v1[0]);
		if (flag) Query(v2[0]);
		return;
	}
	
	rep(x,0,sz(v1)) swap(v1[x],v1[rng()%(x+1)]);
	rep(x,0,sz(v2)) swap(v2[x],v2[rng()%(x+1)]);
	
	vector<int> l1,l2,r1,r2;
	
	int half=1;
	while (half<sz(v1)) half<<=1;
	half>>=1;
	
	rep(x,0,half){
		l1.push_back(v1[x]);
	}
	rep(x,half,sz(v1)){
		curr=Query(v1[x]);
		r1.push_back(v1[x]);
	}
	
	if (!flag){
		for (auto &it:v2){
			int temp=Query(it);
			
			if (temp==curr){
				l2.push_back(it);
			}
			else{
				r2.push_back(it);
				curr=temp;
			}
		}
		
		rec(l1,l2,true),rec(r2,r1,false);
	}
	else{
		for (auto &it:v2){
			int temp=Query(it);
			
			if (temp==curr){
				l2.push_back(it);
			}
			else{
				r2.push_back(it);
				Query(it);
			}
		}
		
		rec(l1,l2,false),rec(r2,r1,false);
	}
}

 
void Solve(int n) {
	vector<int> v1,v2;
	
	rep(x,1,2*n+1){
		int temp=Query(x);
		
		if (temp==curr){
			v2.push_back(x);
		}
		else{
			v1.push_back(x);
		}
		
		curr=temp;
	}
	
	rec(v1,v2,true);
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	10 ms	640 KB	Output is correct
4	Correct	15 ms	896 KB	Output is correct
5	Correct	39 ms	1432 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct
15	Incorrect	78 ms	3788 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct
15	Incorrect	78 ms	3788 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct
15	Incorrect	78 ms	3788 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct
15	Incorrect	78 ms	3788 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct
15	Incorrect	78 ms	3788 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	10 ms	640 KB	Output is correct
8	Correct	15 ms	896 KB	Output is correct
9	Correct	39 ms	1432 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	21 ms	1152 KB	Output is correct
12	Correct	32 ms	1536 KB	Output is correct
13	Correct	29 ms	1536 KB	Output is correct
14	Correct	32 ms	1448 KB	Output is correct
15	Incorrect	78 ms	3788 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Submission #250193

Compilation message