Submission #230195

#	Time	Username	Problem	Language	Result	Execution time	Memory
230195		imnoob	Xylophone (JOI18_xylophone)	C++14	47 / 100	86 ms	384 KiB

xylophone

#include "xylophone.h"
#define MIN(i, j) (i < j ? i : j)
#define MAX(i, j) (i > j ? i : j) 
#include <bits/stdc++.h>

//static int A[5000];
bool visit[5005];
int ans[5005];
int N;

int tanya(int i, int j) {
	return query(MIN(i, j), MAX(i, j));
}

void got(int a, int i, int j) {
	int res1, res2;
	res1 = tanya(a, i);
	if(visit[ans[i] + res1] == 1 || ans[i] + res1 > N) {
		ans[a] = ans[i] - res1;
		return;
	} 
	if(visit[ans[i] - res1] == 1 || ans[i] - res1 < 1) {
		ans[a] = ans[i] + res1;
		return;
	}
	res2 = tanya(a, j);
	if(ans[i] > ans[j]) {
		if(ans[i] + res1 - ans[j] == res2) {
			ans[a] = ans[i] + res1;
		}else ans[a] = ans[i] - res1;
	}else {
		if(ans[j] - ans[i] + res1 == res2) {
			ans[a] = ans[i] - res1;
		}else ans[a] = ans[i] + res1;
	}
}

void solve(int n) {
	N = n;
	//binser
	int l = 1, r = N - 1, pos1, last1, last2 = 1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(tanya(mid, N) == N - 1) {
			l = mid + 1;
			pos1 = mid;
		}else {
			r = mid - 1;
		}
	}
	ans[pos1] = 1;
	if(pos1 > 1) {
		ans[pos1 - 1] = tanya(pos1 - 1, pos1) + 1;
		visit[1] = 1, visit[ans[pos1 - 1]] = 1;
		for(int i = pos1 - 2; i > 0; i--) {
			got(i, i + 1, i + 2);
		}
	}
	ans[pos1 + 1] = tanya(pos1 + 1, pos1) + 1;
	visit[ans[pos1 + 1]] = 1;
	for(int i = pos1 + 2; i <= N; i++) {
		got(i, i - 1, i - 2);
	}
	for(int i = 1; i <= N; i++) {
		answer(i, ans[i]);
	}

}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:41:30: warning: unused variable 'last1' [-Wunused-variable]
  int l = 1, r = N - 1, pos1, last1, last2 = 1;
                              ^~~~~
xylophone.cpp:41:37: warning: unused variable 'last2' [-Wunused-variable]
  int l = 1, r = N - 1, pos1, last1, last2 = 1;
                                     ^~~~~
xylophone.cpp:12:14: warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false [-Wstrict-overflow]
  return query(MIN(i, j), MAX(i, j));
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
xylophone.cpp:12:14: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
  return query(MIN(i, j), MAX(i, j));
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
xylophone.cpp:53:24: warning: 'pos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ans[pos1 - 1] = tanya(pos1 - 1, pos1) + 1;
                   ~~~~~^~~~~~~~~~~~~~~~

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