#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
void solve(int n) {
int mn = -1, mx = -1;
int low = 1, high = n;
while (low <= high) {
int mid = (low + high) / 2;
if (query(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 (query(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;
if (mn > 1) {
sol[mn - 1] = query(mn - 1, mn) + 1;
}
for (int i = mn - 2; i >= 1; i--) {
if (sol[i + 1] < sol[i + 2]) {
int x = query(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 + 2] - x;
if (1 <= delta && delta <= sol[i + 1] && used[delta] == 0 && sol[i + 1] - delta == query(i, i + 1)) {
sol[i] = delta;
used[delta] = 1;
} else {
delta = sol[i + 1] + x;
assert(sol[i + 2] <= delta && delta <= n && used[delta] == 0);
used[delta] = 1;
sol[i] = delta;
}
} else {
int val = sol[i + 1] + query(i, i + 1);
assert(used[val] == 0);
used[val] = 1;
sol[i] = val;
}
} else { /// sol[i + 1] > sol[i + 2]
int x = query(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 >= sol[i + 2] && delta <= n && used[delta] == 0 && query(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] - query(i, i + 1);
assert(used[val] == 0);
used[val] = 1;
sol[i] = val;
}
}
}
if (mn + 1 < mx) {
sol[mn + 1] = sol[mn] + query(mn, mn + 1);
}
for (int i = mn + 2; i <= n; i++) {
if (i == mx) {
continue;
}
if (sol[i - 1] > sol[i - 2]) {
int x = query(i - 2, i);
cout << x << "\n";
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] == query(i, i - 1)) {
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] - query(i - 1, i);
sol[i] = val;
assert(used[val] == 0);
used[val] = 1;
}
} else { /// sol[i - 2] > sol[i - 1]
int x = query(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] == query(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] + query(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 |
0 ms |
208 KB |
Output is correct |
| 2 |
Execution timed out |
1 ms |
208 KB |
Time limit exceeded (wall clock) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Execution timed out |
1 ms |
208 KB |
Time limit exceeded (wall clock) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Execution timed out |
1 ms |
208 KB |
Time limit exceeded (wall clock) |
| 3 |
Halted |
0 ms |
0 KB |
- |
