oj.uz

답안 #63071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63071 2018-07-31T16:04:21 Z shoemakerjo Xylophone (JOI18_xylophone) C++14
0 / 100
 5 ms 480 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 5010

bool taken[maxn];
int ans[maxn];

void solve(int N) {

	//call query on range s to t
	//call answer setting index i to a


	int small = 1;
	for (int inc = (1 << 14); inc > 0; inc /= 2) {
		if (small + inc > N) continue;
		int nx = small + inc;
		int qu = query(nx, N);
		if (qu == N-1) {
			//did not go too far
			small = nx;
		}
	}
	// cout << "small: " << small << endl;
	ans[small] = 1;
	taken[1] = true;
	if (small != 1) {
		ans[small-1] = query(small-1, small)+1;
		taken[ans[small-1]] = true;
	}
	if (small != N) {
		ans[small+1] = query(small, small+1)+1;
		taken[ans[small-1]] = true;
	}
	for (int i = small-2; i >= 1; i--) {
		int nx = i+1;
		int nx2 = i+2;
		int q1 = query(i, nx); //reverse inputs for other direction

		int op1 = ans[nx] + q1; //is greater
		int op2 = ans[nx] - q1; //is less 
		if (taken[op1] || op1 < 1 || op1 > N) {
			ans[i] = op2;
			taken[op2] = true;
			continue;
		}
		if (taken[op2] || op2 < 1 || op2 > N) {
			ans[i] = op1;
			taken[op1] = true;
			continue;
		}

		int q2 = query(i, nx2);
		if (q2 == abs(ans[nx]-ans[nx2])) {
			//nothing changed (i am between them)
			if (ans[nx2] > ans[nx]) {
				ans[i] = op1;
				taken[op1] = true;
				continue;
			}
			else {
				ans[i] = op2;
				taken[op2] = true;
				continue;
			}
		}
		else {
			//something happened
			if (abs(op1 - ans[nx2]) == q2) {
				ans[i] = op1;
				taken[op1] = true;

			}
			else {
				ans[i] = op2;
				taken[op2] = true;
			}
		}


	}
	for (int i = small+2; i <= N; i++) {
		int nx = i-1;
		int nx2 = i-2;

		int q1 = query(nx, i); //reverse inputs for other direction

		int op1 = ans[nx] + q1; //is greater
		int op2 = ans[nx] - q1; //is less 
		if (taken[op1] || op1 < 1 || op1 > N) {
			ans[i] = op2;
			taken[op2] = true;
			continue;
		}
		if (taken[op2] || op2 < 1 || op2 > N) {
			ans[i] = op1;
			taken[op1] = true;
			continue;
		}

		int q2 = query(nx2, i);
		if (q2 == abs(ans[nx]-ans[nx2])) {
			//nothing changed (i am between them)
			if (ans[nx2] > ans[nx]) {
				ans[i] = op1;
				taken[op1] = true;
				continue;
			}
			else {
				ans[i] = op2;
				taken[op2] = true;
				continue;
			}
		}
		else {
			//something happened
			if (abs(op1 - ans[nx2]) == q2) {
				ans[i] = op1;
				taken[op1] = true;

			}
			else {
				ans[i] = op2;
				taken[op2] = true;
			}
		}

	}

	for (int i = 1; i <= N; i++) {
		// cout << "answering: " << i << ":    " << ans[i] << endl;
		answer(i, ans[i]);
	}



}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 5 ms 480 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 5 ms 480 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 5 ms 480 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -