Submission #133272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
133272	2019-07-20T10:26:47 Z	hamzqq9	Minerals (JOI19_minerals)	C++14	40 / 100	106 ms	6712 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;
	vector<int> on(n,0);

	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

	while(1) {

		bool flag2=1;

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

			if(t==1) {

				for(int i=sz(A)-1;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) ask[(qu[x].st+qu[x].nd)>>1].pb(x);

					}

					ask[i].clear();

					cnt=Query(p[A[i]]);

				}

			}
			else {

				for(int i=0;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) ask[(qu[x].st+qu[x].nd)>>1].pb(x);

					}

					ask[i].clear();

				}

			}

			bool flag=0;

			for(int i=0;i<sz(A);i++) flag|=(sz(ask[i])>0);

			if(!flag) {flag2=0;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	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	888 KB	Output is correct
4	Correct	17 ms	1656 KB	Output is correct
5	Correct	35 ms	2808 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 KB	Output is correct
15	Incorrect	106 ms	6712 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 KB	Output is correct
15	Incorrect	106 ms	6712 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 KB	Output is correct
15	Incorrect	106 ms	6712 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 KB	Output is correct
15	Incorrect	106 ms	6712 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 KB	Output is correct
15	Incorrect	106 ms	6712 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	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	888 KB	Output is correct
8	Correct	17 ms	1656 KB	Output is correct
9	Correct	35 ms	2808 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	22 ms	2040 KB	Output is correct
12	Correct	37 ms	2936 KB	Output is correct
13	Correct	35 ms	2940 KB	Output is correct
14	Correct	35 ms	2808 KB	Output is correct
15	Incorrect	106 ms	6712 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Submission #133272

Compilation message