Submission #170374

#	Time	Username	Problem	Language	Result	Execution time	Memory
170374		workharder	Minerals (JOI19_minerals)	C++14	25 / 100	34 ms	3960 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=86005;
int lo[MAXN],hi[MAXN],arr[MAXN],res[MAXN];
vector<int> mid[MAXN];

int tengah(int x,int y){
	return (3*x+2*y)/5;
}

void Solve(int N) {
	int prev=0,tmpL=1,tmpR=N+1,nxt,sudah=0,C=0;
	vector<int> v;
	for(int i=1;i<=2*N;i++)v.push_back(i);
	random_shuffle(v.begin(),v.end());
	for(auto i : v){
		if(tmpL==N+1 || Query(i)==prev){
			arr[tmpR]=i;
			lo[tmpR]=C+1;
			hi[tmpR]=tmpL-1;
			if(lo[tmpR]<hi[tmpR])mid[tengah(lo[tmpR],hi[tmpR])].push_back(tmpR);
			else{
				Answer(i,arr[tmpL-1]);
				sudah++;
			}
			tmpR++;
			if(tmpL==tmpR-N)C=tmpL;
		}
		else{
			arr[tmpL]=i;
			tmpL++;
			prev++;
		}
	}
	if(sudah==N)return;
	int prefix=0;
	while(sudah<N){
		for(int i=1;i<=N;i++){
			prev=Query(arr[i]);
			while(!mid[i].empty()){
				int now=mid[i].back();
				mid[i].pop_back();
				nxt=Query(arr[now]);
				if(prefix){
					if(nxt==prev){   //sudah ada
						hi[now]=i-1;
						res[now]=i;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
						}
					}
					else{
						lo[now]=i+1;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
						}
					}
				}
				else{
					if(nxt==prev){
						lo[now]=i+1;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
						}
					}
					else{
						hi[now]=i-1;
						res[now]=i;
						if(lo[now]<=hi[now])mid[tengah(lo[now],hi[now])].push_back(now);
						else{
							sudah++;
							Answer(arr[now],arr[res[now]]);
						}
					}
				}
				if(sudah==N)return;
				prev=nxt;
			}
		}
		prefix=1-prefix;
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 25 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10