| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1267554 | trvhung | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include "xylophone.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define bit(mask, i) ((mask >> i) & 1)
#define el '\n'
#define F first
#define S second
template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};
const int N = 5e3 + 5;
int a[N];
bool ok[N];
int findV(int x, int y, int i) {
int diff = query(min(y, i), max(y, i));
if (a[y] + diff > n || ok[a[y] + diff]) {
a[i] = a[y] - diff;
ok[a[i]] = 1;
return;
}
if (a[y] - diff < 1 || ok[a[y] - diff]) {
a[i] = a[y] + diff;
ok[a[i]] = 1;
return;
}
int diff2 = query(min(x, i), max(x, i));
if (abs(a[y] - a[x]) == diff2) {
a[i] = (a[y] < a[x] ? a[y] + diff : a[y] - diff);
ok[a[i]] = 1;
}
else if (diff + abs(a[y] - a[x]) == diff2) {
a[i] = (a[y] < a[x] ? a[y] - diff : a[y] + diff);
ok[a[i]] = 1;
}
else {
int v = a[y] - diff, c = 0;
if (max({v, a[y], a[x]}) - min({v, a[y], a[x]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
v = a[y] + diff;
if (max({v, a[y], a[x]}) - min({v, a[y], a[x]}) == diff2) {
a[i] = v;
ok[a[i]] = 1;
c++;
}
assert(c == 1);
}
}
void solve(int n) {
int l = 1, r = n, L = -1, R = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(1, mid) == n - 1) {
R = mid;
r = mid - 1;
} else l = mid + 1;
}
l = 1, r = R - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(mid, R) == n - 1) {
L = mid;
l = mid + 1;
} else r = mid - 1;
}
ok[1] = ok[n] = 1;
a[L] = 1, a[R] = n;
if (L > 1) {
int v = 1 + query(L - 1, L);
a[L - 1] = v; ok[v] = 1;
}
if (L < n && L + 1 != R) {
int v = 1 + query(L, L + 1);
a[L + 1] = v; ok[v] = 1;
}
if (R > 1 && a[R - 1] == 0) {
int v = n - query(R - 1, R);
a[R - 1] = v; ok[v] = 1;
}
if (R < n) {
int v = n - query(R, R + 1);
a[R + 1] = v; ok[v] = 1;
}
for (int i = R - 2; i >= 1; --i) {
if (a[i] > 0) continue;
a[i] = findV(i + 2, i + 1, i);
}
for (int i = R + 2; i <= n; ++i)
a[i] = findV(i - 2, i - 1, i);
for (int i = 1; i <= n; ++i)
answer(i, a[i]);
}