Submission #133732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
133732	2019-07-21T09:07:54 Z	hamzqq9	Minerals (JOI19_minerals)	C++14	40 / 100	100 ms	6244 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]]);
 
					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;
 
				}
 
			}
 
		}
 
		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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 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	8 ms	1028 KB	Output is correct
4	Correct	17 ms	1656 KB	Output is correct
5	Correct	36 ms	2724 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	100 ms	6244 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	100 ms	6244 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	100 ms	6244 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	100 ms	6244 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	100 ms	6244 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	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	5 ms	632 KB	Output is correct
7	Correct	8 ms	1028 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	36 ms	2724 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	23 ms	2040 KB	Output is correct
12	Correct	37 ms	2684 KB	Output is correct
13	Correct	36 ms	2764 KB	Output is correct
14	Correct	36 ms	2680 KB	Output is correct
15	Incorrect	100 ms	6244 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Submission #133732

Compilation message