Submission #433653

#	Time	Username	Problem	Language	Result	Execution time	Memory
433653		AmineTrabelsi	Xylophone (JOI18_xylophone)	C++14	0 / 100	3 ms	200 KiB

xylophone

#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] = N;
	//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 < five){
		int q = query(one,one+1);
		A[one+1] = 1+q;
		prev = q;
	}
	for(int i=one+2;i<five;i++){
		int q = query(i,i+1);
		int sq = query(one,i);
		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++) {
		cerr<<A[i] << ' ';
	}cerr<<'\n';

	if(five+1 <= N){
		int q = query(five,five+1);
		A[five+1] = N-q;
		prev = q;
	}
	for(int i = 1; i <= N; i++) {
		cerr<<A[i] << ' ';
	}cerr<<'\n';

	for(int i=five+2;i<=N;i++){
		int q = query(i-1,i);
		int sq = query(five,i);
		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++) {
		cerr<<A[i] << ' ';
	}cerr<<'\n';
	for(int i = 1; i <= N; i++) {
		answer(i, A[i]);
	}
}

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