Submission #433723

#	Time	Username	Problem	Language	Result	Execution time	Memory
433723		AmineTrabelsi	Xylophone (JOI18_xylophone)	C++14	0 / 100	3037 ms	536 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int A[5005];
bool cant[5005];
set<int> poss[5005];
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;
	cant[1] = 1; 
	cant[N] = 1;
	poss[one].insert(1);
	poss[five].insert(N);
	int cnt = N-2;
	for(int i=one-1;i>=1;i--){
		int q = query(i,i+1);
		for(auto x:poss[i+1]){
			int nx = x+q;
			if(nx > 1 && nx < N && !cant[nx]){
				poss[i].insert(nx);
			}
			nx = x-q;
			if(nx > 1 && nx < N && !cant[nx]){
				poss[i].insert(nx);
			}
		}
		if(poss[i].size() == 1){
			cnt--;
			A[i] = *(poss[i].begin());
			cant[A[i]] = 1;
		}
	}
	for(int i=one+1;i<five-1;i++){
		int q = query(i-1,i);
		for(auto x:poss[i-1]){
			int nx = x+q;
			if(nx > 1 && nx < N && !cant[nx]){
				poss[i].insert(nx);
			}
			nx = x-q;
			if(nx > 1 && nx < N && !cant[nx]){
				poss[i].insert(nx);
			}
		}
		if(poss[i].size() == 1){
			cnt--;
			A[i] = *(poss[i].begin());
			cant[A[i]] = 1;
		}
	}
	if(five-1 > one){
		int q = query(five-1,five);
		A[five-1]= N-q;
		cant[A[five-1]] = 1;
		poss[five-1].insert(A[five-1]);
		cnt--;
	}
	for(int i=five+1;i<=N;i++){
		int q = query(i-1,i);
		for(auto x:poss[i-1]){
			int nx = x+q;
			if(nx > 1 && nx < N && !cant[nx]){
				poss[i].insert(nx);
			}
			nx = x-q;
			if(nx > 1 && nx < N && !cant[nx]){
				poss[i].insert(nx);
			}
		}
		if(poss[i].size() == 1){
			cnt--;
			A[i] = *(poss[i].begin());
			cant[A[i]] = 1;
		}
	}
	while(cnt){
		for(int i=1;i<=N;i++){
			vector<int> er;
			for(auto x:poss[i]){
				if(cant[x])er.push_back(x);
			}
			for(auto x:er)poss[i].erase(x);
			if(poss[i].size() == 1){
				cnt--;
				A[i] = *(poss[i].begin());
				cant[A[i]] = 1;
			}
		}
	}
	for(int i = 1; i <= N; i++) {
		cerr<<i<<": ";
		for(auto x:poss[i]){
			cerr<<x<<" ";
		}
		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