Submission #1272756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272756		coderpemula	Xylophone (JOI18_xylophone)	C++17	100 / 100	20 ms	456 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
using namespace std;

bool vis[10001];
int ans[5001],arr[5001];
//void init(int n){
//	for(int i=1;i<=n;i++) cin>>arr[i];
//}
//int query(int a, int b){
//	int mx = 0, mn = 1e9;
//	for(int i=a;i<=b;i++) mx = max(mx,arr[i]), mn =min(mn,arr[i]);
//	return mx-mn;
//}
void solve(int N) {
	int n = N;
	if(n == 2){
		answer(1, 1);
		answer(2, 2);
		return;
	}
  	int i,j,t;
	vis[1] = vis[0] = true;
	for(i=n+1;i<=2*n;i++) vis[i] = true;
	int now = 1,id = 2,x;
	int L = 2, R = n,M;
	bool ada = false;
	while(L <= R){
		M = (L+R)/2;
		x = query(M,n);
		if(x == n-1) L = M+1;
		else{
			ada = true;
			now = M-1;
			R = M-1;
		}
	}
	//cout<<now<<endl;
	if(!ada) now = 1;
	ans[now] = 1;
	int one = now;
	// traverse right
	if(now == n-1){
		ans[n] = n;
		vis[n] = true;
	}
	else{
		id = now+1;
		x = query(now, id);
		ans[id] = x+1;
		vis[ans[id]] = true;
		while(true){
			if(id == n) break;
			x = query(id, id+1);
			// might be ans[id]+x or ans[id]-x
			// so we check bos
		//	cout<<id<<" "<<id+1<<" "<<x<<" :"<<endl;
			if(ans[id]-x <= 1){
				ans[id+1] = ans[id]+x;
				vis[ans[id+1]] = true;
				id++;
				continue;
			}
			if(vis[ans[id]-x]){
				ans[id+1] = ans[id]+x;
				vis[ans[id+1]] = true;
				id++;
				continue;
			}
			if(vis[ans[id]+x]){
				ans[id+1] = ans[id]-x;
				vis[ans[id+1]] = true;
				id++;
				continue;
			}
//			if(ans[id]+x == n){
//				ans[id+1] = n;
//				vis[ans[id+1]] = true;
//				id++;
//				continue;
//			}
			// kita gatau ini + atau - jadi kita cek
			int bil = x;
			x = query(id-1, id+1);
			if(ans[id-1] < ans[id]){
				// min max
				if(x == ans[id] - ans[id-1]){
					// berarti middle
					//cout<<"CEK\n";
					ans[id+1] = ans[id]-bil;
					vis[ans[id+1]] = true;
					id++;
					continue;
				}
				if(x == bil){
					ans[id+1] = ans[id]-bil;
					vis[ans[id+1]] = true;
					id++;
					continue;
				}
				ans[id+1] = ans[id]+bil;
				vis[ans[id+1]] = true;
				id++;
			}
			else{
				if(x == ans[id-1] - ans[id]){
					ans[id+1] = ans[id]+bil;
					vis[ans[id+1]] = true;
					id++;
					continue;
				}
				if(x == bil){
					ans[id+1] = ans[id]+bil;
					vis[ans[id+1]] = true;
					id++;
					continue;
				}
				ans[id+1] = ans[id]-bil;
				vis[ans[id+1]] = true;
				id++;
			}
		}
	}
	if(now > 1){
		id = now-1;
		x = query(id, now);
		ans[id] = x+1;
		vis[ans[id]] = true;
		while(true){
			if(id == 1) break;
			x = query(id-1, id);
			if(ans[id]-x <= 1){
				ans[id-1] = ans[id]+x;
				vis[ans[id-1]] = true;
				id--;
				continue;
			}
			if(vis[ans[id]-x]){
				ans[id-1] = ans[id]+x;
				vis[ans[id-1]] = true;
				id--;
				continue;
			}
			if(vis[ans[id]+x]){
				ans[id-1] = ans[id]-x;
				vis[ans[id-1]] = true;
				id--;
				continue;
			}
			// kita gatau
			int bil = x;
			x = query(id-1, id+1);
			if(ans[id+1] > ans[id]){
				// min max
				if(x == ans[id+1]-ans[id]){
					ans[id-1] = ans[id]+bil;
					vis[ans[id-1]] = true;
					id--;
					continue;
				}
				if(x > bil){
					ans[id-1] = ans[id]-bil;
					vis[ans[id-1]] = true;
					id--;
					continue;
				}
				ans[id-1] = ans[id]+bil;
				vis[ans[id-1]] = true;
				id--;
			}
			else{
				// max min
				if(x == ans[id]-ans[id+1]){
					ans[id-1] = ans[id]-bil;
					vis[ans[id-1]] = true;
					id--;
					continue;
				}
				if(bil == x){
					ans[id-1] = ans[id]-bil;
					vis[ans[id-1]] = true;
					id--;
					continue;
				}
				ans[id-1] = ans[id]+bil;
				vis[ans[id-1]] = true;
				id--;
			}
		}
	}
	for(i=1;i<=n;i++) answer(i, ans[i]);
//	for(i=1;i<=n;i++) cout<<ans[i]<<" ";
//	cout<<endl;
}

//int main()
//{
//	int n;
//	cin>>n;
//	init(n);
//	solve(n);
//	
//	return 0;
//}

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