제출 #1356034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356034		crispxx	Xylophone (JOI18_xylophone)	C++20	47 / 100	17 ms	464 KiB

xylophone

#include "xylophone.h"

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

int ask(int l, int r) {
	return query(l + 1, r + 1);
}

int find_one(int n) {
	int l = 0, r = n - 1;
	
	while(l < r) {
		int mid = (l + r + 1) >> 1;
		
		if(ask(mid, n - 1) == n - 1) l = mid;
		else r = mid - 1;
	}
	
	return l;
}

void solve(int n) {
	int i1 = find_one(n);
	
	vector<int> a(n);
	
	a[i1] = 1;
	
	vector<array<int, 2>> dif(n);
	
	for(int i = 0; i < n; i++) {
		if(i >= 1) dif[i][0] = ask(i - 1, i);
		if(i >= 2) dif[i][1] = ask(i - 2, i);
	}
	
	for(int i = i1 + 1; i < n; i++) {
		if(i == i1 + 1) {
			a[i] = a[i - 1] + dif[i][0];
		} else {
			
			if(a[i - 2] < a[i - 1]) {
				if(dif[i - 1][0] + dif[i][0] == dif[i][1]) {
					a[i] = a[i - 1] + dif[i][0];
				} else {
					a[i] = a[i - 1] - dif[i][0];
				}
			} else {
				if(dif[i - 1][0] + dif[i][0] == dif[i][1]) {
					a[i] = a[i - 1] - dif[i][0];
				} else {
					a[i] = a[i - 1] + dif[i][0];
				}
			}
			
		}
	}
	
	for(int i = i1 - 1; i >= 0; i--) {
		if(i == i1 - 1) {
			a[i] = a[i + 1] + dif[i + 1][0];
		} else {
			
			if(a[i + 2] < a[i + 1]) {
				if(dif[i + 2][0] + dif[i + 1][0] == dif[i + 2][1]) {
					a[i] = a[i + 1] + dif[i + 1][0];
				} else {
					a[i] = a[i + 1] - dif[i + 1][0];
				}
			} else {
				if(dif[i + 2][0] + dif[i + 1][0] == dif[i + 2][1]) {
					a[i] = a[i + 1] - dif[i + 1][0];
				} else {
					a[i] = a[i + 1] + dif[i + 1][0];
				}
			}
			
		}
	}
	
	// cout << "here: " << nl;
	
	// for(int i = 0; i < n; i++) {
		// cout << a[i] << ' ';
	// }
	
	// cout << nl;
	
	for(int i = 0; i < n; i++) answer(i + 1, a[i]);
}

/**

**/

• 서브태스크 1: 11 / 11
• 서브태스크 2: 36 / 36
• 서브태스크 3: 0 / 53