| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 981341 | Amaarsaa | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int a[5002], ans[5002];
int query(int l, int r) {
int mx, mn;
mx = mn= a[l];
for (int j = l; j <= r; j ++) mx = max(mx, a[j]), mn = min(mn, a[j]);
return mx - mn;
}
void solve(int N) {
int ind, mid,i, s,x1, x2, p, n = N, lo, hi;
lo = 1;
hi = n;
int b[5005], c[5005], ens[5005];
while (lo < hi) {
mid = (lo + hi)/2;
if ( query(1, mid) == n - 1) hi = mid;
else lo = mid + 1;
}
ind = lo;
ans[1] = 0;
ans[2] = 0 + query(1, 2);
int mx = ans[2];
for ( i = 3; i <= n; i ++) {
s = query(i - 1, i);
p = query(i - 2, i);
b[i]= s;
c[i] = p;
x1 = ans[i - 1] - s;
x2 = ans[i - 1] + s;
if ( max(x1, max(ans[i - 1], ans[i - 2])) - min(x1, min(ans[i - 1], ans[i - 2])) == p) {
ans[i] = x1;
}
if ( max(x2, max(ans[i - 1], ans[i - 2])) - min(x2, min(ans[i - 1], ans[i - 2])) == p) {
ans[i] = x2;
}
mx = max(mx,ans[i]);
}
int j = 1;
for (i = 1; i <= n; i ++) {
ens[i] = ans[i]= ans[i] + (n - mx);
if ( ans[i] == n) j = i;
}
sort ( ens + 1, ens + n + 1);
int can = 1;
for (i =1; i <= n; i ++) if ( ens[i] != i) can = 0;
if ( can && j == ind) {
// for (i = 1; i <= n; i ++) cout << ans[i] << " ";
for (i = 1; i <= n; i ++) answer(i, ans[i]);
return ;
}
ans[1] = 0;
ans[2] = -ans[2];
mx = 0;
for ( i = 3; i <= n; i ++) {
s = b[i];
p = c[i];
x1 = ans[i - 1] - s;
x2 = ans[i - 1] + s;
if ( max(x1, max(ans[i - 1], ans[i - 2])) - min(x1, min(ans[i - 1], ans[i - 2])) == p) {
ans[i] = x1;
}
if ( max(x2, max(ans[i - 1], ans[i - 2])) - min(x2, min(ans[i - 1], ans[i - 2])) == p) {
ans[i] = x2;
}
mx = max(mx,ans[i]);
}
for (i = 1; i <= n; i ++) ans[i] = ans[i] + (n - mx);
// for (i = 1; i <= n; i ++) cout << ans[i] << " ";
for (i =1 ; i<= n; i++) answer(i, ans[i]);
}