Submission #133738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
133738	2019-07-21T09:10:59 Z	hamzqq9	Minerals (JOI19_minerals)	C++14	40 / 100	103 ms	6284 KB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 500005
#define MOD 998244353
#define KOK 700		
using namespace std;
 
void Solve(int n) {
 
	n<<=1;
 
	mt19937 rnd(time(NULL));
 
	vector<int> p;
	vector<int> gr(n);
	vector<ii> qu(n);
	vector<vector<int>> ask(n);
	vector<int> A,B;
 
	for(int i=1;i<=n;i++) p.pb(i);
 
	shuffle(p.begin(),p.end(),rnd);
 
	int cnt=0;
	
	for(int i=0;i<n;i++) {
 
		int cur=Query(p[i]);
 
		if(cur>cnt) {
 
			gr[i]=0;
			A.pb(i);
			
		}
		else {
 
			gr[i]=1;
 
			qu[i]={0,sz(A)-1};
 
			if(qu[i].st!=qu[i].nd) ask[(qu[i].st+qu[i].nd)>>1].pb(i);
 
			B.pb(i);
 
		}
 
		cnt=cur;
 
	}
 
	// values in vectors are just indices not permuation values
 
	int last=sz(A)-1;

	while(1) {
 
		bool flag2=1;
 
		for(int t=1;t<=2;t++) {

			int has=0;

			for(int i=0;i<sz(A);i++) has+=sz(ask[i]);

			if(!has) {

				flag2=0;

				break ;

			}
 
			if(t==1) {
 
				for(int i=last;i>=0;i--) {
 
					for(auto x:ask[i]) {
 
						int cur=Query(p[x]);
 
						if(cur!=cnt) {
 
							qu[x].st=i+1;
 
						}
						else {
 
							qu[x].nd=i;
 
						}
 
						cnt=cur;
 
						if(qu[x].st!=qu[x].nd) {
						
							int mid=(qu[x].st+qu[x].nd)>>1;

							if(mid>i) --has;

							ask[mid].pb(x);
 						
 						}

					}
 
					ask[i].clear();

					if(!has) break ;
 					
 					last=i;

					cnt=Query(p[A[i]]);
 
				}
 
			}
			else {
 
				for(int i=last;i<sz(A);i++) {
 
					cnt=Query(p[A[i]]);

					last=i;
 
					for(auto x:ask[i]) {
 
						int cur=Query(p[x]);
 
						if(cur!=cnt) {
 
							qu[x].st=i+1;
 
						}
						else {
 
							qu[x].nd=i;
 
						}
 
						cnt=cur;
 
						if(qu[x].st!=qu[x].nd) {
						
							int mid=(qu[x].st+qu[x].nd)>>1;

							if(mid<i) --has;

							ask[mid].pb(x);
 						
 						}

					}
 
					ask[i].clear();

					if(!has) break ;
 
				}
 
			}
 
		}
 
		if(!flag2) break ;
	
	}
 
	for(int i:B) {
 
		int pos=qu[i].st;
 
		Answer(p[A[pos]],p[i]);
 
	}
 
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	5 ms	632 KB	Output is correct
3	Correct	9 ms	1016 KB	Output is correct
4	Correct	17 ms	1548 KB	Output is correct
5	Correct	36 ms	2680 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	103 ms	6284 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	103 ms	6284 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	103 ms	6284 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	103 ms	6284 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	103 ms	6284 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	296 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	9 ms	1016 KB	Output is correct
8	Correct	17 ms	1548 KB	Output is correct
9	Correct	36 ms	2680 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	27 ms	1912 KB	Output is correct
12	Correct	37 ms	2680 KB	Output is correct
13	Correct	36 ms	2728 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	103 ms	6284 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Submission #133738

Compilation message