Submission #537427

#	Time	Username	Problem	Language	Result	Execution time	Memory
537427		chaoyue	Library (JOI18_library)	C++14	19 / 100	62 ms	208 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;

int n;
vector<int> v;

int findedge(){
	int split;
	deque<int> a((int)v.size()); //a is included array, implicit discarded array
	vector<int> ma(n, 0), mb(n, 0); //ma is query array for a, mb is query array for b
	for(int i=0; i<(int)v.size(); i++){
		a[i] = v[i];
		ma[v[i]] = 1;
	}
	while((int)a.size() > 1){
		//cut a in half and get result
		split = ((int)a.size()-1) / 2;  //2nd half of a will be discarded, 1st half (including split) will be included
		for(int i=split+1; i<(int)a.size(); i++){
			ma[a[i]] = 0;
			mb[a[i]] = 1;
		}
		if(Query(ma) >= Query(mb)){  //take remain
			for(int i=split+1; i<(int)a.size(); i++){
				a.pop_back();
			}
		}
		else{  //take discarded
			for(int i=split+1; i<(int)a.size(); i++){
				ma[a[i]] = 1;
				mb[a[i]] = 0;
			}
			for(int i=0; i<=split; i++){
				ma[a[0]] = 0;
				mb[a[0]] = 1;
				a.pop_front();
			}
		}
	}
	return a[0];
}

void Solve(int N){
	n = N;
	int tmp, l=0, r=n-1;
	vector<int> ans(n), m(n, 0);
	v.resize(n);
	if(n > 200){
		Answer(ans);
		return;
	}
	for(int i=0; i<n; i++){
		v[i] = i;
	}
	for(int i=0; i<n; i++){
		tmp = findedge();
		//cout<<"tmp: "<<tmp<<endl;
		v.erase(find(v.begin(), v.end(), tmp));
		if(!l){
			ans[l] = tmp;
			l++;
		}
		else{
			//Query l and tmp
			m[ans[l-1]] = 1;
			m[tmp] = 1;
			if(Query(m) == 1){
				m[ans[l-1]] = 0;
				ans[l] = tmp;
				l++;
			}
			else{
				m[ans[l-1]] = 0;
				ans[r] = tmp;
				r--;
			}
			m[tmp] = 0;
		}
	}
	for(int i=0; i<n; i++){
		ans[i]++;
	}
	Answer(ans);
}

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