Submission #654431

#	Time	Username	Problem	Language	Result	Execution time	Memory
654431		minhnhatnoe	Xylophone (JOI18_xylophone)	C++14	100 / 100	72 ms	208 KiB

xylophone

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

namespace interact{
	void A(int pos, int val){
		// cout << pos << ": " << val+1 << endl;
		answer(pos+1, val+1);
		// cout << "FIN" << endl;
	}
	int Q(int l, int r){
		return query(l+1, r+1);
	}
};
int find_n(int n){
	int l = 0, r = n-1;
	int last = interact::Q(0, n-1);
	while (l < r){
		int m = (l+r)>>1;
		int q = interact::Q(0, m);
		if (last == q){
			r = m;
		}
		else{
			l = m+1;
		}
	}
	// cout << "P: " << l << endl;
	return l;
}
void solve(int n){
	vector<bool> a(n);
	int posmax = find_n(n);
	interact::A(posmax, n-1);
	int last = n-1, last1;
	a.back() = 1;
	for (int i=posmax-1; i>=0; i--){
		int cdelta = interact::Q(i, i+1);
		int first = last - cdelta;
		int second = last + cdelta;
		int realval;
		if (first < 0 || a[first]){
			realval = second;
		}
		else if (second >= n || a[second]){
			realval = first;
		}
		else{
			int cdelta1 = interact::Q(i, i+2);
			if (cdelta1 == cdelta + abs(last - last1)){
				// last1 -> last -> i
				if (last1 > last){
					// last > i
					realval = first;
				}
				else{
					realval = second;
				}
			}
			else{
				if (last1 < last){
					realval = first;
				}
				else{
					realval = second;
				}
			}
		}
		interact::A(i, realval);
		last1 = last;
		last = realval;
		a[realval] = true;
	}
	last = n-1;
	for (int i=posmax+1; i<n; i++){
		int cdelta = interact::Q(i-1, i);
		int first = last - cdelta;
		int second = last + cdelta;
		int realval;
		if (first < 0 || a[first]){
			realval = second;
		}
		else if (second >= n || a[second]){
			realval = first;
		}
		else{
			int cdelta1 = interact::Q(i-2, i);
			if (cdelta1 == cdelta + abs(last - last1)){
				// last1 -> last -> i
				if (last1 > last){
					// last > i
					realval = first;
				}
				else{
					realval = second;
				}
			}
			else{
				if (last1 < last){
					realval = first;
				}
				else{
					realval = second;
				}
			}
		}
		interact::A(i, realval);
		last1 = last;
		last = realval;
		a[realval] = true;
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:52:5: warning: 'last1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     if (last1 > last){
      |     ^~

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