Submission #650501

#	Time	Username	Problem	Language	Result	Execution time	Memory
650501		Koful123	Xylophone (JOI18_xylophone)	C++17	47 / 100	93 ms	480 KiB

xylophone

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

void solve(int n){
	int l = 1,r = n;
	vector<int> v(n+1),th(n+1),se(n+1),vis(n+1,0);
	while(l < r){
		int m = (l + r) / 2;
		if(query(1,m) == n-1) r = m;
		else l = m + 1;
	}		
	v[l] = n; vis[v[l]] = 1;
	if(l != n){
		se[l+1] = query(l,l+1);
		v[l+1] = n - se[l+1]; vis[v[l+1]] = 1;
	}
	for(int i=l+2;i<=n;i++){
		se[i] = query(i-1,i);
		if(v[i-1] + se[i] > n){
			v[i] = v[i-1] - se[i]; vis[v[i]] = 1; continue;
		}
		if(v[i-1] - se[i] <= 0){
			v[i] = v[i-1] + se[i]; vis[v[i]] = 1; continue;
		}
		if(vis[v[i-1] - se[i]]){
			v[i] = v[i-1] + se[i]; vis[v[i]] = 1; continue;
		}
		if(vis[v[i-1] + se[i]]){
			v[i] = v[i-1] - se[i]; vis[v[i]] = 1; continue;
		}

		th[i] = query(i-2,i);
		if(th[i] == se[i-1]){
			v[i] = v[i-1] + (v[i-2] > v[i-1] ? se[i] : -se[i]);
		}
		else{
			if(v[i-2] > v[i-1]){
				if(se[i] == th[i]) v[i] = v[i-1] + se[i];
				else v[i] = v[i-1] - se[i];
			}
			else{
				if(th[i] == se[i]) v[i] = v[i-1] - se[i];
				else v[i] = v[i-1] + se[i];;
			}
		}
	}

	if(l != 1){
		se[l-1] = query(l-1,l);
		v[l-1] = n - se[l-1]; vis[v[l-1]] = 1;
	}	

	for(int i=l-2;i>=1;i--){
		se[i] = query(i,i+1),th[i] = query(i,i+2);
		if(th[i] == se[i+1]){
			v[i] = v[i+1] + (v[i+2] > v[i+1] ? se[i] : -se[i]);
		}
		else{
			if(v[i+2] > v[i+1]){
				if(se[i] == th[i]) v[i] = v[i+1] + se[i];
				else v[i] = v[i+1] - se[i];
			}
			else{
				if(th[i] == se[i]) v[i] = v[i+1] - se[i];
				else v[i] = v[i+1] + se[i];
			}
		}
	}
	for(int i=1;i<=n;i++){
		answer(i,v[i]);
	}
}

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