oj.uz

답안 #433642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433642 2021-06-20T09:05:08 Z AmineTrabelsi Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 200 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
	/*
	int value = query(1, N);

	for(int i = 1; i <= N; i++) {
		answer(i, i);
	}
	*/
	int low = 1,high = N;
	/*
	// prefix
	while(low != high){
		int mid = (low+high)/2;
		if(query(1,mid) == N-1){
			high = mid;
		}else low = mid+1;
	}
	int five = high;
	*/
	low = 1, high = N;
	while(low != high){
		int mid = (low+high+1)/2;
		if(query(mid,N) == N-1){
			low = mid;
		}else high = mid-1;
	}
	int one = low;
	vector<int> A(N+1,0);
	A[one] = 1;
	//A[five] = 5;
	//cerr<< low <<" "<<high<< '\n';
	int prev = 1;
	if(one > 1){
		int q = query(one-1,one);
		A[one-1] = 1+q;
		prev = q;
	}
	for(int i=one-2;i>=1;i--){
		int q = query(i,i+1);
		int sq = query(i,one);
		if(sq > prev){
			A[i] = A[i+1]+q;
		}else{
			A[i] = A[i+1]-q;
		}
		prev = sq;
	}
	if(one+1 <= N){
		int q = query(one,one+1);
		A[one+1] = 1+q;
		prev = q;
	}
	for(int i=one+2;i<=N;i++){
		int q = query(i,i-1);
		int sq = query(i,one);
		if(sq > prev){
			A[i] = A[i+1]+q;
		}else{
			A[i] = A[i+1]-q;
		}
		prev = sq;
	}
	for(int i = 1; i <= N; i++) {
		answer(i, A[i]);
	}
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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