제출 #71286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71286		ekrem	Xylophone (JOI18_xylophone)	C++98	100 / 100	143 ms	956 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas + son + 1)/2)
#define NMAX 1000005
using namespace std;

// static const int N_MAX = 5000;
// static const int Q_MAX = 10000;
// static int N;
// static int A[N_MAX];
// static bool used[N_MAX];
// static int query_c;
// static int answer_c;



// int query(int s, int t) {
// 	if(query_c >= Q_MAX) {
// 		printf("Wrong Answer\n");
// 		exit(0);
// 	}
// 	query_c++;
// 	if(!(1 <= s && s <= t && t <= N)) {
// 		printf("Wrong Answer\n");
// 		exit(0);
// 	}
// 	int mx = 0, mn = N + 1;
// 	for(int i = s - 1; i < t; i++) {
// 		if(mx < A[i]) {
// 			mx = A[i];
// 		}
// 		if(mn > A[i]) {
// 			mn = A[i];
// 		}
// 	}
// 	return mx - mn;
// }

// void answer(int i, int a) {
// 	cout << a << " oldu" << endl;
// 	answer_c++;
// 	if(!(1 <= i && i <= N)) {
// 		printf("Wrong Answerwww\n");
// 		exit(0);
// 	}
// 	if(!(1 <= a && a <= N)) {
// 		printf("Wrong Answerqqqq\n");
// 		exit(0);
// 	}
// 	if(used[i - 1]) {
// 		printf("Wrong Answerasd\n");
// 		exit(0);
// 	}
// 	if(a != A[i - 1]) {
// 		printf("Wrong Answerrrr\n");
// 		exit(0);
// 	}
// 	used[i - 1] = true;
// }

int a[NMAX], v[NMAX];

void solve(int n) {
	int i = 1;
	int bas = 1;
	int son = n - 1;
	while(bas < son){
		int cvp = query(orta, n);
		// cout << orta << " " << cvp << endl;
		if(cvp == n - 1)
			bas = orta;
		else
			son = orta - 1;
	}
	i = orta;
	answer(i, 1);
	a[i] = 1;
	v[1] = 1;
	// cout << i << endl;
	if(i > 1){
		int cvp = query(i - 1, i);
		answer(i - 1, cvp + 1);
		a[i - 1] = cvp + 1;
		v[cvp + 1] = 1;
	}
	if(i < n){
		int cvp = query(i, i + 1);
		answer(i + 1, cvp + 1);
		a[i + 1] = cvp + 1;
		v[cvp + 1] = 1;
	}
	for(int j = i - 2; j >= 1; j--){
		int y = query(j, j + 1);
		int aa = a[j + 1];
		int bb = a[j + 2];
		int mx = max(aa, bb);
		int mn = min(aa, bb);
		int p1 = aa + y;
		int p2 = aa - y;
		int son = -1;
		if(v[p1])
			son = p2;
		else if(v[p2])
			son = p1;
		else{
			int x = query(j, j + 2);
			if(max(mx, p1) - min(mn, p1) != x)
				son = p2;
			if(max(mx, p2) - min(mn, p2) != x)
				son = p1;
		}
		assert(son != -1);
		answer(j, son);
		a[j] = son;
		v[son] = 1;

	}
	for(int j = i + 2; j <= n; j++){
		int y = query(j - 1, j);
		int aa = a[j - 1];
		int bb = a[j - 2];
		int mx = max(aa, bb);
		int mn = min(aa, bb);
		int p1 = aa + y;
		int p2 = aa - y;
		int son = -1;
		if(v[p1])
			son = p2;
		else if(v[p2])
			son = p1;
		else{
			int x = query(j - 2, j);
			if(max(mx, p1) - min(mn, p1) != x)
				son = p2;
			if(max(mx, p2) - min(mn, p2) != x)
				son = p1;
		}
		assert(son != -1);
		answer(j, son);
		a[j] = son;
		v[son] = 1;

	}

}


// int main() {
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	query_c = 0;
// 	answer_c = 0;
// 	if(scanf("%d", &N) != 1) {
// 		fprintf(stderr, "Error while reading input\n");
// 		exit(1);
// 	}
// 	for(int i = 0; i < N; i++) {
// 		if(scanf("%d", A + i) != 1) {
// 			fprintf(stderr, "Error while reading input\n");
// 			exit(1);
// 		}
// 		used[i] = false;
// 	}
// 	solve(N);
// 	if(!(answer_c == N)) {
// 		printf("Wrong Answer\n");
// 		exit(0);
// 	}
// 	printf("Accepted : %d\n", query_c);
// }

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