Submission #704238

#	Time	Username	Problem	Language	Result	Execution time	Memory
704238		minhcool	Xylophone (JOI18_xylophone)	C++17	100 / 100	66 ms	568 KiB

xylophone

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937_64 rng(7405);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, a[N];

bool choose[N];

bool valid(int x){
	return (x >= 1 && x <= n && !choose[x]);
}

int answerr[N];
set<int> inq;

void solve(int N){
	n = N;
	int l = 2, r = n;
	while(l < r){
		int mid = (l + r) >> 1;
		if(query(1, mid) < (n - 1)) l = mid + 1;
		else r = mid;
	}
	int le = 1, ri = l - 1;
	while(le < ri){
		int mid = (le + ri + 1) >> 1;
		if(query(mid, l) == (n - 1)) le = mid;
		else ri = mid - 1;
	}
	int temp1 = le, temp2 = l;
	//cout << temp1 << " " << temp2 << "\n";
	answerr[temp1] = 1, answerr[temp2] = n;
	if(temp1 > 1) inq.insert(temp1 - 1);
	if(temp1 < (temp2 - 1)) inq.insert(temp1 + 1);
	if(temp1 < (temp2 - 2)) inq.insert(temp2 - 1);
	if(temp2 < n) inq.insert(temp2 + 1);
	choose[1] = choose[n] = 1;
	while(inq.size()){
		int pos = rnd(1, inq.size()), temp = -1;
		for(auto it : inq){
			pos--;
			if(!pos){
				temp = it;
				break;
			}
		}
		if(answerr[temp - 1]){
			int diff = query(temp - 1, temp);
			if(!valid(answerr[temp - 1] - diff)) answerr[temp] = answerr[temp - 1] + diff;
			else if(!valid(answerr[temp - 1] + diff)) answerr[temp] = answerr[temp - 1] - diff;
			else{
				assert(temp >= 2 && answerr[temp - 2]);
				int diff2 = query(temp - 2, temp);
				if(answerr[temp - 2] < answerr[temp - 1]){
					if(diff2 == (answerr[temp - 1] - answerr[temp - 2])) answerr[temp] = answerr[temp - 1] - diff;
					else{
						if(diff2 == diff) answerr[temp] = answerr[temp - 1] - diff;
						else answerr[temp] = answerr[temp - 1] + diff;
					}
				}
				else{
					if(diff2 == (answerr[temp - 2] - answerr[temp - 1])) answerr[temp] = answerr[temp - 1] + diff;
					else{
						if(diff2 == diff) answerr[temp] = answerr[temp - 1] + diff;
						else answerr[temp] = answerr[temp - 1] - diff;
					}
				}
			}
		}
		else{
			//int diff = query(temp, temp + 1);
			int diff = query(temp, temp + 1);
			if(!valid(answerr[temp + 1] - diff)) answerr[temp] = answerr[temp + 1] + diff;
			else if(!valid(answerr[temp + 1] + diff)) answerr[temp] = answerr[temp + 1] - diff;
			else{
				assert(answerr[temp + 2]);
				int diff2 = query(temp, temp + 2);
				if(answerr[temp + 2] < answerr[temp + 1]){
					if(diff2 == (answerr[temp + 1] - answerr[temp + 2])) answerr[temp] = answerr[temp + 1] - diff;
					else{
						if(diff2 == diff) answerr[temp] = answerr[temp + 1] - diff;
						else answerr[temp] = answerr[temp + 1] + diff;
					}
				}
				else{
					if(diff2 == (answerr[temp + 2] - answerr[temp + 1])) answerr[temp] = answerr[temp + 1] + diff;
					else{
						if(diff2 == diff) answerr[temp] = answerr[temp + 1] + diff;
						else answerr[temp] = answerr[temp + 1] - diff;
					}
				}
			}
		}
		choose[answerr[temp]] = 1;
		//cout << "OK " << temp << " " << answerr[temp] << "\n";
		inq.erase(temp);
		if(temp >= 2 && !answerr[temp - 1]) inq.insert(temp - 1);
		if(temp < n && !answerr[temp + 1]) inq.insert(temp + 1);
	}
	for(int i = 1; i <= n; i++){
		//cout << i << " " << answerr[i] << "\n";
		answer(i, answerr[i]);
	}
}

Compilation message (stderr)

xylophone.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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