| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 363180 | buyolitsez | 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.
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
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, const vector<T> &a) {
for (auto &i : a) {
out << i << " ";
}
return out;
}
template<typename T, typename D>
istream &operator>>(istream &in, pair<T, D> &a) {
in >> a.first >> a.second;
return in;
}
template<typename T, typename D>
ostream &operator<<(ostream &out, const pair<T, D> &a) {
out << a.first << " " << a.second;
return out;
}
struct LogOutput {
template<typename T>
LogOutput &operator<<(const T &x) {
#ifdef DIVAN
cout << x;
#endif
return *this;
}
} dout, fout;
typedef long long ll;
typedef unsigned long long ull;
typedef double dl;
typedef complex<double> cd;
#define nl '\n'
#define elif else if
#define all(_v) _v.begin(), _v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)(v.size())
#define sqr(_v) ((_v) * (_v))
#define vpi vector<pair<int, int>>
#define eb emplace_back
#define pb push_back
#define mod(x, m) ((x) >= 0 ? ((x) % m) : ((((x) % m) + m) % m))
#define vi vector<int>
#define pi pair<int, int>
#define ti tuple<int, int, int>
#define minq(x, y) x = min((x), (y))
#define maxq(x, y) x = max(x, (y))
#define forn(i, n) for (int i = 0; i < (n); ++i)
const ll INFL = 9187201950435737471;
const ll nINFL = -9187201950435737472;
const int INF = 2139062143;
const int nINF = -2139062144;
const ull ULINF = numeric_limits<ull>::max();
const long double PI = acos(-1);
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline void IO() {
#ifdef DIVAN
freopen("../input.txt", "r", stdin);
freopen("../output.txt", "w", stdout);
#else
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
}
void answer(int a, int b) {
cout << a << ' ' << b << endl;
}
int query(int a, int b) {
cout << a << ' ' << b << endl;
int x;
cin >> x;
return x;
}
bool Check(int a, int b, int c, int i) {
if (a > b && b > c) {
return query(i + 1, i + 3) == a - c;
}
if (a > c && c > b) {
return query(i + 1, i + 3) == a - b;
}
if (c > a && a > b) {
return query(i + 1, i + 3) == c - b;
}
if (c > b && b > a) {
return query(i + 1, i + 3) == c - a;
}
if (b > a && a > c) {
return query(i + 1, i + 3) == b - c;
}
if (b > c && c > a) {
return query(i + 1, i + 3) == b - a;
}
}
int GetRight(int n, int a, int b, int x, int i) {
int c1 = b + x, c2 = b - x;
if (c1 > n) {return c2;}
if (c2 < 1) {return c1;}
if (Check(a, b, c1, i)) {
return c1;
}
return c2;
}
int GetLeft(int n, int a, int b, int x, int i) {
int c1 = b + x, c2 = b - x;
if (c1 > n) {return c2;}
if (c2 < 1) {return c1;}
if (Check(c1, a, b, i)) {
return c1;
}
return c2;
}
void solve(int n) {
int pos = n - 1;
while (query(1, pos) == n - 1) {
--pos;
}
vector <int> num1(n), num2(n);
// dout << "pos = " << pos << '\n';
num1[pos] = n;
num2[pos] = 1;
bool f1 = 1, f2 = 1;
if (pos + 1 < n) {
int x = query(pos + 1, pos + 2);
num1[pos + 1] = n - x;
num2[pos + 1] = 1 + x;
}
vector <vi> cand1(n), cand2(n);
for (int i = pos + 2; i < n; ++i) {
int x = query(pos + 2, pos + 3);
num1[i] = GetRight(n, num1[i - 2], num1[i], x, i - 2);
num2[i] = GetRight(n, num2[i - 2], num2[i], x, i - 2);
}
if (pos != 0) {
int x = query(pos, pos + 1);
num1[pos - 1] = n - x;
num2[pos - 1] = 1 + x;
}
for (int i = pos - 2; i >= 0; --i) {
int x = query(i + 1, i + 2);
num1[i] = GetLeft(n, num1[i + 1], num1[i + 2], x, i);
num2[i] = GetLeft(n, num2[i + 1], num2[i + 2], x, i);
}
set <int> q1, q2;
forn(i, n) {
q1.insert(num1[i]);
q2.insert(num2[i]);
}
if (q1.count(0) || sz(q1) != n) {
f1 = 0;
}
if (q2.count(0) || sz(q2) != n) {
f2 = 0;
}
assert(f1 ^ f2);
if (f1) {
forn(i, n) {
answer(i + 1, num1[i]);
}
} else {
forn(i, n) {
answer(i + 1, num2[i]);
}
}
}
void Solve() {
int n;
cin >> n;
solve(n);
}
signed main() {
// IO();
int t = 1;
// cin >> t;
int startTime = clock();
for (int i = 1; i <= t; ++i) {
// cout << "Case #" << i << ": ";
Solve();
}
int endTime = clock();
fout << '\n' << "Time: " << (endTime - startTime + 999) / 1000;
return 0;
}