Submission #120709

#	Time	Username	Problem	Language	Result	Execution time	Memory
120709		imyujin	Minerals (JOI19_minerals)	C++14	100 / 100	50 ms	3708 KiB

minerals

#include "minerals.h"
#include<vector>
#include<map>

using namespace std;

#define MAXN 43005

int q[2*MAXN];
vector<int> L, R;
vector<bool> chk;

vector<int> f(vector<int> lidx, int rs, int re, bool in){
	//printf("[%d %d]", rs, re);
	//for(auto a:lidx) printf("%d ", a);
	//printf("\n");
	if(rs==re) return lidx;
	int m=(int)(rs+(double)(re-rs)*0.62);
	vector<int> q(re-rs+2), lef, rig;
	for(int i=m+1; i<=re; i++) q[re-rs+1]=Query(R[i]);
	for(int i=re-rs; i>0; i--){
		q[i]=Query(L[lidx[i]]);
		if(in){
			if(q[i]!=q[i+1]) rig.push_back(lidx[i]);
			else lef.push_back(lidx[i]);
		}
		else{
			if(q[i]!=q[i+1]) lef.push_back(lidx[i]);
			else rig.push_back(lidx[i]);
		}
	}
	if(lef.size()<m-rs+1) lef.push_back(lidx[0]);
	else rig.push_back(lidx[0]);
	vector<int> v1, v2;
	v1=f(lef, rs, m, in);
	v2=f(rig, m+1, re, !in);
	for(auto a:v2) v1.push_back(a);
	return v1;
}

void Solve(int N) {
	for(int i=1; i<=2*N; i++) chk.push_back(false);
	for(int i=1; i<=2*N; i++){
		q[i]=Query(i);
		if(q[i]>q[i-1]) L.push_back(i);
		else R.push_back(i);
	}
	//for(auto a:L) printf("%d ", a);
	//printf("\n");
	vector<int> v(N);
	for(int i=0; i<N; i++) v[i]=i;
	vector<int> ans=f(v, 0, N-1, true);
	//for(auto a:ans) printf("{%d}", a);
	for(int i=0; i<N; i++) Answer(L[ans[i]], R[i]);
}

Compilation message (stderr)

minerals.cpp: In function 'std::vector<int> f(std::vector<int>, int, int, bool)':
minerals.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(lef.size()<m-rs+1) lef.push_back(lidx[0]);
     ~~~~~~~~~~^~~~~~~

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