Submission #742091

#	Time	Username	Problem	Language	Result	Execution time	Memory
742091		onebit1024	Xylophone (JOI18_xylophone)	C++17	47 / 100	143 ms	444 KiB

xylophone

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

// static int A[5000];

void solve(int n) {

	vector<int>a(n+1);
	int pos = 1;
	for(int i = n-1;i>=1;--i){
		if(query(i,n)==(n-1)){
			pos = i;
			break;
		}
	}
	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: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53