Submission #48068

#	Time	Username	Problem	Language	Result	Execution time	Memory
48068		jacobtpl	Library (JOI18_library)	C++14	100 / 100	489 ms	716 KiB

library

#include "library.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
#define INFLL 1000000000000000100ll
#define UQ(x) (x).resize(distance((x).begin(),unique(all((x)))))
#define mid(x,y) (((x)+(y))>>1)
#define M 1000000007ll
int n;
int lquery(vector<int> v) {
	vector<int> m(n,0);
	for (int x:v) {
		m[x]=1;
	}
	return Query(m);
}
vector<vector<int> > v;
int rquery(int i,int j) {
	vector<int> m(n,0);
	for (int k=i;k<=j;k++) {
		for (int x:v[k]) m[x]=1;
	}
	return Query(m);
}
int query2(int a,int b) {
	vector<int> m(n,0);
	m[a]=1;
	m[b]=1;
	return Query(m);
}
vector<int> merge(int a,int b) {
	vector<int> x;
	if (sz(v[a])==1 && sz(v[b])==1) {
		x.pb(v[a][0]);
		x.pb(v[b][0]);
		return x;
	}
	if (sz(v[a])>sz(v[b])) swap(a,b);
	if (sz(v[a])==1) {
		if (query2(v[a][0],v[b][0])==1) {
			x.pb(v[a][0]);
			for (int y:v[b]) x.pb(y);
		} else {
			//*******
			//assert(query2(v[a][0],v[b].back())==1);
			//*******
			for (int y:v[b]) x.pb(y);
			x.pb(v[a][0]);
		}
		return x;
	}
	if (query2(v[a][0],v[b][0])==1) {
		for (int y:v[a]) x.pb(y);
		reverse(all(x));
		for (int y:v[b]) x.pb(y);
	} else if (query2(v[a].back(),v[b].back())==1) {
		for (int y:v[a]) x.pb(y);
		for (int i=sz(v[b])-1;i>=0;i--) x.pb(v[b][i]);
	} else if (query2(v[a][0],v[b].back())==1) {
		for (int y:v[a]) x.pb(y);
		reverse(all(x));
		for (int i=sz(v[b])-1;i>=0;i--) x.pb(v[b][i]);
	} else {
		//*******
		//assert(query2(v[a].back(),v[b][0])==1);
		//*******
		for (int y:v[a]) x.pb(y);
		for (int y:v[b]) x.pb(y);
	}
	return x;
}
void Solve(int N) {
	n=N;
	for (int i=0;i<n;i++) {
		vector<int> x;
		x.pb(i);
		v.pb(x);
	}
	#ifdef DEBUG
	for (vector<int> x:v) {
		printf("{ ");
		for (int y:x) printf("%d ", y+1);
		printf("} ");
	}
	printf("\n");
	#endif
	while(sz(v)>1) {
		int b=0,e=sz(v)-1;
		int idx=e;
		while(b<e+1) {
			int m=(b+e)/2;
			int r=rquery(0,m);
			if (r<(m+1)) {
				idx=min(idx,m);
				e=m-1;
			} else b=m+1;
		}
		b=0,e=idx;
		int idx2=0;
		while(b<e+1) {
			int m=(b+e)/2;
			int r=rquery(m,idx);
			if (r<(idx-m+1)) {
				idx2=max(idx2,m);
				b=m+1;
			} else e=m-1;
		}
		assert(idx2<idx);
		vector<int> x=merge(idx2,idx);
		v.erase(v.begin()+idx);
		v.erase(v.begin()+idx2);
		v.pb(x);
		#ifdef DEBUG
		for (vector<int> x:v) {
			printf("{ ");
			for (int y:x) printf("%d ", y+1);
			printf("} ");
		}
		printf("\n");
		#endif
	}
	assert(sz(v)==1);
	assert(sz(v[0])==n);
	
	vector<int> res(n);
	for(int i = 0; i < n; i++) {
		res[i] = v[0][i]+1;
	}
	Answer(res);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81