제출 #230202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230202		Nightlight	Xylophone (JOI18_xylophone)	C++14	100 / 100	80 ms	512 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(ans[i] + res1 > N || visit[ans[i] + res1] == 1) {
		ans[a] = ans[i] - res1;
		return;
	} 
	if(ans[i] - res1 < 1 || visit[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);
			visit[ans[i]] = 1;
		}
	}
	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);
		visit[ans[i]] = 1;
	}
	for(int i = 1; i <= N; i++) {
		answer(i, ans[i]);
	}
}

컴파일 시 표준 에러 (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:41:24: warning: 'pos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int l = 1, r = N - 1, pos1, last1, last2 = 1;
                        ^~~~

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