Submission #516557

#	Time	Username	Problem	Language	Result	Execution time	Memory
516557		drkarlicio2107	Xylophone (JOI18_xylophone)	C++14	100 / 100	66 ms	436 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int bio [5010]; int l [5010];
int moze (int x, int n){
	if (x>n || x<1) return 0;
	if (bio[x]) return 0;
	return 1;
}
int moze2 (int x, int y, int diff1, int diff2){
	int z1=y+diff1, z2=y-diff1;
	if (max (abs(x-y), max(abs (x-z1), abs (y-z1)))==diff2) return z1;
	return z2;
}
void solve (int n){
	int lo=1; int hi=n;
	while (hi-lo>1){
		//cout << lo << " " << hi;
		int mid=(lo+hi)/2;
		int x=query (mid, n);
		if (x==n-1) lo=mid;
		else hi=mid-1;
	}
	if (hi!=lo){
		if (query (hi, n)==n-1) lo++;
	}
	//cout << lo;
	bio [1]=1; l[lo]=1;
	for (int i=lo+1; i<n+1; i++){
		int x=query (i-1, i);
		if (moze (l[i-1]+x, n) && moze (l[i-1]-x, n)){
			int y=query (i-2, i);
			l[i]=moze2 (l[i-2], l[i-1], x, y); bio [moze2 (l[i-2], l[i-1], x, y)]=1;
		}
		else{
			if (moze(l[i-1]+x, n)){
				l[i]=l[i-1]+x; bio [l[i-1]+x]=1;
			}
			else{
				l[i]=l[i-1]-x; bio [l[i-1]-x]=1;
			}
		}
	}
	for (int i=lo-1; i>0; i--){
		int x=query (i, i+1);
		if (moze (l[i+1]+x, n) && moze (l[i+1]-x, n)){
			int y=query (i, i+2);
			l[i]=moze2 (l[i+2], l[i+1], x, y); bio [moze2 (l[i+2], l[i+1], x, y)]=1;
		}
		else{
			if (moze(l[i+1]+x, n)){
				l[i]=l[i+1]+x; bio [l[i+1]+x]=1;
			}
			else{
				l[i]=l[i+1]-x; bio [l[i+1]-x]=1;
			}
		}
	}
	for (int i=1; i<n+1; i++) answer (i, l[i]);
}

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