답안 #250193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #250193

Compilation message