| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 907464 | andro | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include <bits/stdc++.h>
#include "xylophone.h"
//using namespace std;
static int a[5000];
static int A[5000];
/*
int query(int l, int r) {
int mn = 5000, mx = 0;
for(int i = l; i <= r; i++) {
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
return mx - mn;
}
void answer(int index, int value) {
A[index] = value;
}*/
void aaa(int index, int value) {
A[index] = value;
}
void solve(int N) {
// answer index, value
int l = 1, r = N, p = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(query(mid, N) == N - 1) {
l = mid + 1;
p = mid;
}
else {
r = mid - 1;
}
}
int id1 = p;
aaa(p, 1);
answer(p, 1);
l = 1, r = N, p = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(query(1, mid) == N - 1) {
r = mid - 1;
p = mid;
}
else {
l = mid + 1;
}
}
int idn = p;
answer(p, N);
aaa(p, N);
int mn = N;
int mx = 0;
for(int i = id1 - 1; i > 0; i--) {
int u = query(i, id1);
if(u > mx) {
answer(i, u + 1);
aaa(i, u + 1);
}
else {
int x = query(i, i + 1);
if(x + A[i + 1] > 1 && x + A[i + 1] < N) {
answer(i, x + A[i + 1]);
aaa(i, x + A[i + 1]);
}
else {
answer(i, A[i + 1] - x);
aaa(i, A[i + 1] - x);
}
}
}
mn = N;
for(int i = idn + 1; i <= N; i++) {
int u = query(idn, i);
if(u < mn) {
answer(i, N - u);
}
else {
// na intervalu mn + 1, N sigurno
int x = query(i - 1, i);
if(x + A[i - 1] > mn && x + A[i - 1] < N) {
answer(i, x + A[i - 1]);
aaa(i, x + A[i - 1]);
}
else {
answer(i, A[i - 1] - x);
aaa(i, A[i - 1] - x);
}
}
mn = min(mn, u);
}
mn = N;
for(int i = idn - 1; i > id1; i--) {
int u = query(i, idn);
if(u < mn) {
answer(i, N - u);
aaa(i, N - u);
}
else {
int x = query(i, i + 1);
if(x + A[i + 1] > mn && x + A[i + 1] < N) {
answer(i, x + A[i + 1]);
aaa(i, x + A[i + 1]);
}
else {
answer(i, A[i + 1] - x);
aaa(i, A[i + 1] - x);
}
}
mn = min(mn, u);
}
}
/*
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
solve(n);
cout << "\n";
for(int i = 1; i <= n; i++) {
cout << A[i] << " ";
}
}*/