#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
/// 2 * log(N) + 2 * (N - 6) + 4
map<pair<int, int>, int> mp;
int ask(int l, int r) {
if (mp.count({l, r}) > 0) {
return mp[{l, r}];
}
int x = query(l, r);
mp[{l, r}] = x;
return x;
}
void solve(int n) {
mp.clear();
int mn = -1, mx = -1;
int low = 1, high = n;
while (low <= high) {
int mid = (low + high) / 2;
if (ask(1, mid) == n - 1) {
mx = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
low = 1, high = mx - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (ask(mid, mx) == n - 1) {
mn = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
assert(mn != -1 && mx != -1 && mn < mx);
vector<int> sol(n + 1, 0);
vector<bool> used(n + 1, 0);
sol[mn] = 1;
sol[mx] = n;
used[1] = used[n] = 1;
if (mn > 1) {
sol[mn - 1] = ask(mn - 1, mn) + 1;
used[sol[mn - 1]] = 1;
}
for (int i = mn - 2; i >= 1; i--) {
if (sol[i + 1] < sol[i + 2]) {
int x = ask(i, i + 2);
if (x != sol[i + 2] - sol[i + 1]) {
///its less than sol[i + 1] or greater than sol[i + 2]
int delta = sol[i + 1] + x;
if (delta <= n && delta >= sol[i + 1] && used[delta] == 0) {
sol[i] = delta;
used[delta] = 1;
} else {
delta = sol[i + 2] - x;
assert(sol[i + 1] >= delta && delta <= n && used[delta] == 0);
used[delta] = 1;
sol[i] = delta;
}
} else {
int val = sol[i + 1] + ask(i, i + 1);
assert(used[val] == 0);
used[val] = 1;
sol[i] = val;
}
} else { /// sol[i + 1] > sol[i + 2]
int x = ask(i, i + 2);
if (x != sol[i + 1] - sol[i + 2]) {
///its less than sol[i + 2] or greater than sol[i + 1]
int delta = sol[i + 1] - x;
if (delta >= 1 && delta <= sol[i + 2] && used[delta] == 0 && ask(i, i + 1) == x) {
used[delta] = 1;
sol[i] = delta;
} else {
delta = sol[i + 2] + x;
assert(delta <= n && delta >= sol[i + 1] && used[delta] == 0);
used[delta] = 1;
sol[i] = delta;
}
} else {
int val = sol[i + 1] - ask(i, i + 1);
assert(used[val] == 0);
used[val] = 1;
sol[i] = val;
}
}
}
if (mn + 1 < mx) {
sol[mn + 1] = sol[mn] + ask(mn, mn + 1);
used[sol[mn + 1]] = 1;
}
if (mx - 1 > mn + 1) {
sol[mx - 1] = sol[mx] - ask(mx - 1, mx);
used[sol[mx - 1]] = 1;
}
if (mx + 1 <= n) {
sol[mx + 1] = sol[mx] - ask(mx, mx + 1);
used[sol[mx + 1]] = 1;
}
for (int i = mn + 2; i <= n; i++) {
if (sol[i] != 0) {
continue;
}
if (sol[i - 1] > sol[i - 2]) {
int x = ask(i - 2, i);
if (x != sol[i - 1] - sol[i - 2]) {
///its less than sol[i - 2] or greater than sol[i - 1]
int delta = sol[i - 2] + x;
if (delta <= n && delta >= sol[i - 1] && used[delta] == 0 && delta - sol[i - 1] == ask(i - 1, i)) {
sol[i] = delta;
used[delta] = 1;
} else {
sol[i] = sol[i - 1] - x;
assert(1 <= sol[i] && sol[i] < sol[i - 2] && used[sol[i]] == 0);
used[sol[i]] = 1;
}
} else {
int val = sol[i - 1] - ask(i - 1, i);
sol[i] = val;
assert(used[val] == 0);
used[val] = 1;
}
} else { /// sol[i - 2] > sol[i - 1]
int x = ask(i - 2, i);
if (x != sol[i - 2] - sol[i - 1]) {
///its less than sol[i - 1] or greater than sol[i - 2]
int delta = sol[i - 1] + x;
if (delta <= n && delta >= sol[i - 2] && used[delta] == 0 && delta - sol[i - 1] == ask(i - 1, i)) {
sol[i] = delta;
used[delta] = 1;
} else {
sol[i] = sol[i - 2] - x;
assert(1 <= sol[i] && sol[i] < sol[i - 1] && used[sol[i]] == 0);
used[sol[i]] = 1;
}
} else {
int val = sol[i - 1] + ask(i - 1, i);
assert(used[val] == 0);
used[val] = 1;
sol[i] = val;
}
}
}
for (int i = 1; i <= n; i++) {
answer(i, sol[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
2 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
2 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
2 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
