답안 #133738

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

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

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

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

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

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

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

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

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

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

답안 #133738

Compilation message