Submission #565719

#	Time	Username	Problem	Language	Result	Execution time	Memory
565719		almothana05	Xylophone (JOI18_xylophone)	C++14	100 / 100	78 ms	460 KiB

xylophone

#include <cstdio>
#include <cstdlib>
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int num[10006] , vis[10006];
 
void solve(int menge) {
	int be = 1 , en = menge , comp , cmp;
	int st = 1 , ene = menge - 1, mit;
	while(st <= ene){
		int mit = (st + ene)/2;
		// cout << mit << ' ' ;
		cmp = query(mit , en);
		if(cmp != menge - 1){
			ene = mit - 1;
		}
		else{
			st = mit + 1;
		}
	}
	be = ene;
	st = be + 1;
	ene = menge ;
	// cout << "\n";
	
	while(st <= ene){
		int mit = (st + ene)/2;
		// cout << mit << ' ';
		cmp = query(be , mit);
		if(cmp != menge - 1){
			st = mit + 1;
		}
		else{
			ene = mit - 1;
		}
	}
	// cout << "\n";
	en = st;
	vis[1] = 1; vis[menge] = 1;
	num[be] = 1;
	num[en] = menge;
	//cout << be << ' ' << en << "\n";
	if(be > 1){
		num[be - 1] = 1 + query(be - 1 , be);
		vis[num[be - 1]] = 1;
	}
	if(num[be + 1] == 0){
		num[be + 1] = 1 + query(be , be + 1);
		vis[num[be + 1]] = 1;
	}
 
	if(en < menge){
		num[en + 1] = menge - query(en , en + 1);
		vis[num[en + 1]] = 1;
	}
	if(num[en - 1] == 0){
		num[en - 1] = menge - query(en - 1 , en);
		vis[num[en - 1]] = 1;
	}
 
	for(int i = be - 2 ; i > 0 ; i--){
		if(num[i] != 0){
			continue;
		}
		// cout << num[i] << "\n";
		cmp = query(i , i + 1);
		if(vis[num[i + 1] + cmp] == 1){
			num[i] = num[i + 1] - cmp;
			vis[num[i]] = 1;
			continue;
		}
		else if(vis[num[i + 1] - cmp] == 1){
			num[i] = num[i + 1] + cmp;
			vis[num[i]] = 1;
			continue;
		}
		comp = query(i , i + 2);
		if(comp == cmp + abs(num[i + 1] - num[i + 2]) ){
			num[i] = num[i + 1] + (cmp * ( (num[i + 1] - num[i + 2]) / abs(num[i + 1] - num[i + 2]) ) );
			vis[num[i]] = 1;
		}
		else{
			num[i] = num[i + 1] + (-1 * cmp * ( (num[i + 1] - num[i + 2]) / abs(num[i + 1] - num[i + 2]) ) );
			vis[num[i]] = 1;
		}
	}


	for(int i = be + 2 ; i <= menge ; i++){
		if(num[i] != 0){
			continue;
		}
		cmp = query(i - 1 , i);
		
		if(vis[num[i - 1] + cmp] == 1){
			num[i] = num[i - 1] - cmp;
			vis[num[i]] = 1;
			continue;
		}
		else if(vis[num[i - 1] - cmp] == 1){
			num[i] = num[i - 1] + cmp;
			vis[num[i]] = 1;
			continue;
		}

		comp = query(i - 2, i);
		if(comp == cmp + abs(num[i - 1] - num[i - 2]) ){
			num[i] = num[i - 1] + (cmp * ( (num[i - 1] - num[i - 2]) / abs(num[i - 1] - num[i - 2]) ) );
			vis[num[i]] = 1;
		}
		else{
			num[i] = num[i - 1] + (-1 * cmp * ( (num[i - 1] - num[i - 2]) / abs(num[i - 1] - num[i - 2]) ) );
			vis[num[i]] = 1;
		}
	}
		// cout << "ja\n";
	for(int i = 1; i <= menge ; i++){
		assert(num[i] > 0);
		answer(i , num[i]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:10:32: warning: unused variable 'mit' [-Wunused-variable]
   10 |  int st = 1 , ene = menge - 1, mit;
      |                                ^~~

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