| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 905088 | destrikes | Xylophone (JOI18_xylophone) | C++17 | 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.
//#define _GLIBCXX_DEBUG
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroint-loops")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define M_PI 3.141592653589793
#define int int64_t
#define uint unsigned int
#define ld long double
#define nl '\n'
#define yes "YES\n"
#define no "NO\n"
#define szof(x) (int) x.size()
#define pii pair<int, int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define emplace emplace_back
#define fast_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file_input freopen("..\\input.txt","r",stdin);freopen("..\\output.txt","w",stdout);freopen("..\\error.txt","w",stderr);
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#else
mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
template<typename T> using sorted_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename K, typename V> using normal_unordered_map = gp_hash_table<K, V>;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_set_eq = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename K, typename V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename C>
istream &operator>>(istream &in, pair<T, C> &a) {
return in >> a.first >> a.second;
}
template<typename T, typename C>
ostream &operator<<(ostream &out, pair<T, C> &a) {
return out << a.first << ' ' << a.second;
}
template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
for (auto &i: a) {
in >> i;
}
return in;
}
template<typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
for (auto i: a) {
out << i << ' ';
}
return out;
}
template<typename T>
ostream &operator<<(ostream &out, vector<vector<T>> &a) {
for (auto i: a) {
for (auto j: i)
out << j << " ";
out << nl;
}
return out;
}
const int inf = 2e12, mod = 1e9 + 7;
uniform_int_distribution<int> int_distr;
int rnd(int a, int b) { return int_distr(tw) % (b - a + 1) + a; }
void solve() {
int n;
cin >> n;
int r = 0, prev = n - 1;
for (int i = 1; i < n; ++i) {
cout << "? " << i + 1 << " " << n << endl;
int cur;
cin >> cur;
if (cur != prev) {
r = i - 1;
break;
}
}
vector<int> ans(n);
ans[r] = 1;
set<int> used;
used.insert(1);
if (r != 0) {
cout << "? " << r << " " << r + 1 << endl;
int res;
cin >> res;
ans[r - 1] = res + 1;
used.insert(res + 1);
}
if (r != n - 1) {
cout << "? " << r + 1 << " " << r + 2 << endl;
int res;
cin >> res;
ans[r + 1] = res + 1;
used.insert(res + 1);
}
for (int i = r; i + 2 < n; ++i) {
int f = i, s = i + 1, t = i + 2;
cout << "? " << s + 1 << " " << t + 1 << endl;
int dd;
cin >> dd;
// if (ans[s] - dd < 1 || used.contains(ans[s] - dd)) {
// ans[t] = ans[s] + dd;
// used.insert(ans[t]);
// continue;
// } else if (ans[s] + dd > n || used.contains(ans[s] + dd)) {
// ans[t] = ans[s] - dd;
// used.insert(ans[t]);
// continue;
// }
cout << "? " << f + 1 << " " << t + 1 << endl;
int dt;
cin >> dt;
if (dt == dd + abs(ans[s] - ans[f])) {
if (ans[f] < ans[s]) { // ans[t] > ans[s]
ans[t] = ans[s] + dd;
} else {
ans[t] = ans[s] - dd;
}
} else {
if (ans[f] < ans[s]) {// ans[t] < ans[s]
ans[t] = ans[s] - dd;
} else {
ans[t] = ans[s] + dd;
}
}
used.insert(ans[t]);
}
for (int i = r; i > 1; --i) {
int f = i, s = i - 1, t = i - 2;
cout << "? " << t + 1 << " " << s + 1 << endl;
int dd;
cin >> dd;
// if (ans[s] - dd < 1 || used.contains(ans[s] - dd)) {
// ans[t] = ans[s] + dd;
// used.insert(ans[t]);
// continue;
// } else if (ans[s] + dd > n || used.contains(ans[s] + dd)) {
// ans[t] = ans[s] - dd;
// used.insert(ans[t]);
// continue;
// }
cout << "? " << t + 1 << " " << s + 1 << endl;
int dt;
cin >> dt;
if (dt == dd + abs(ans[s] - ans[f])) {
if (ans[f] < ans[s]) { // ans[t] > ans[s]
ans[t] = ans[s] + dd;
} else {
ans[t] = ans[s] - dd;
}
} else {
if (ans[f] < ans[s]) {// ans[t] < ans[s]
ans[t] = ans[s] - dd;
} else {
ans[t] = ans[s] + dd;
}
}
used.insert(ans[t]);
}
cout << "! " << ans << endl;
}
int32_t main() {
#ifdef LOCAL
//file_input
auto start_time = clock();
cerr << setprecision(3) << fixed;
#endif
fast_IO
int test = 1;
//cin >> test;
while (test--) {
solve();
}
#ifdef LOCAL
cerr << "Execution time: " << (clock() - start_time) * (int) 1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}