Submission #516509

#	Time	Username	Problem	Language	Result	Execution time	Memory
516509		drkarlicio2107	Xylophone (JOI18_xylophone)	C++14	0 / 100	0 ms	200 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int bio [5010]; int n; int l [5010];
int moze (int x){
	if (bio[x] || x>n || x<1) return 0;
	return 1;
}
void solve (int n){
	int lo=1; int hi=n;
	while (hi-lo>1){
		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) && moze (l[i-1]-x)){
			int y=query (i-2, i);
			if (y>abs(l[i-1]-l[i-2])){
				if (l[i-1]>l[i-2]){
					l[i]=l[i-2]+y; bio [l[i-2]+y]=1;
				}
				else{
					l[i]=l[i-2]-y; bio [l[i-2]-y]=1;
				}
			}
			else{
				if (l[i-1]>l[i-2]){
					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;
				}
			}
		}
		else{
			if (moze(l[i-1]+x)){
				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) && moze (l[i+1]-x)){
			int y=query (i, i+2);
			if (y>abs(l[i+1]-l[i+2])){
				if (l[i+1]>l[i+2]){
					l[i]=l[i+2]+y; bio [l[i+2]+y]=1;
				}
				else{
					l[i]=l[i+2]-y; bio [l[i+2]-y]=1;
				}
			}
			else{
				if (l[i+1]>l[i+2]){
					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;
				}
			}
		}
		else{
			if (moze(l[i+1]+x)){
				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: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53