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;
const int maxn = 5010;
int a[maxn];
bool done[maxn];
void solve(int n)
{
int l = 1;
int r = n;
int dak = 1;
while (l <= r) {
int mid = (l + r) / 2;
if (query(mid, n) == n - 1) dak = mid, l = mid + 1;
else r = mid - 1;
}
l = dak;
cout << l << endl;
answer(l, 1);
a[l] = 1;
done[1] = true;
for (int i = l - 1; i >= 1; i--) {
int x = query(i, i + 1);
int ans = -1;
if (a[i + 1] - x <= 0 || done[a[i + 1] - x]) ans = a[i + 1] + x;
if (a[i + 1] + x > n || done[a[i + 1] + x]) ans = a[i + 1] - x;
if (ans == -1) {
if (max({a[i + 1] + x, a[i + 1], a[i + 2]}) - min({a[i + 1] + x, a[i + 1], a[i + 2]}) != query(i, i + 2)) ans = a[i + 1] - x;
else ans = a[i + 1] + x;
}
a[i] = ans;
done[ans] = true;
answer(i, a[i]);
}
for (int i = l + 1; i <= n; i++) {
int x = query(i - 1, i);
int ans = -1;
if (a[i - 1] - x <= 0 || done[a[i - 1] - x]) ans = a[i - 1] + x;
if (a[i - 1] + x > n || done[a[i - 1] + x]) ans = a[i - 1] - x;
if (ans == -1) {
if (max({a[i - 1] + x, a[i - 1], a[i - 2]}) - min({a[i - 1] + x, a[i - 1], a[i - 2]}) != query(i - 2, i)) ans = a[i - 1] - x;
else ans = a[i - 1] + x;
}
a[i] = ans;
done[ans] = true;
answer(i, a[i]);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |