Submission #742104

#	Time	Username	Problem	Language	Result	Execution time	Memory
742104		onebit1024	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	208 KiB

xylophone

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

// static int A[5000];
int pos = 1;
void get(int l, int r, int n){
	if(l > r)return;
	if(l==r){
		if(query(l,n))pos = l;
		return;
	}
	int m = (l+r)/2;
	if(query(m,n)==(n-1)) pos = m,get(m+1,r,n);
	else  get(l,m-1,n);
}

void solve(int n) {

	vector<int>a(n+1);
	get(1,n,n);

	a[pos] = 1;
	if(pos > 1)a[pos-1] = 1+query(pos-1,pos);
	if(pos < n)a[pos+1] = 1+query(pos,pos+1);
	vector<int>taken(n+1);
	for(int i = pos-1;i<=pos+1;++i)taken[a[i]] = 1;
	for(int i = pos-2;i>=1;--i){
		set<int>opt;
		int c = query(i,i+1);
		if(a[i+1]-c >= 1 && !taken[a[i+1]-c])opt.insert(a[i+1]-c);
		if(a[i+1]+c <= n && !taken[a[i+1]+c])opt.insert(a[i+1]+c);
		if(opt.size()==1){
			a[i] = *opt.begin();
			taken[a[i]] = 1;
			continue;
		}
		int v = abs(a[i+1]-a[i+2]);
		int w = query(i,i+2);
		if(w==v){
			// a[i] lies between a[i+1] and a[i-1]
			for(auto x : opt){
				if(x >= min(a[i+1],a[i+2]) && x<= max(a[i+1],a[i+2])){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}else{
			for(auto x : opt){
				set<int>kk = {a[i+1],a[i+2],x};
				if((*--kk.end())-*kk.begin() == w){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}
	}
	for(int i = pos+2;i<=n;++i){
		set<int>opt;
		int c = query(i-1,i);
		if(a[i-1]-c >= 1 && !taken[a[i-1]-c])opt.insert(a[i-1]-c);
		if(a[i-1]+c <= n && !taken[a[i-1]+c])opt.insert(a[i-1]+c);
		if(opt.size()==1){
			a[i] = *opt.begin();
			taken[a[i]] = 1;
			continue;
		}
		int v = abs(a[i-1]-a[i-2]);
		int w = query(i-2,i);
		if(w==v){
			// a[i] lies between a[i-1] and a[i-2]
			for(auto x : opt){
				if(x >= min(a[i-1],a[i-2]) && x<= max(a[i-1],a[i-2])){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}else{
			for(auto x : opt){
				set<int>kk = {a[i-1],a[i-2],x};
				if((*--kk.end())-*kk.begin() == w){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}
	}	
	for(int i = 1;i<=n;++i){
		answer(i,a[i]);
	}
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53