Submission #363180

#	Time	Username	Problem	Language	Result	Execution time	Memory
363180		buyolitsez	Xylophone (JOI18_xylophone)	C++17	Compilation error	0 ms	0 KiB

xylophone

#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;
}

Compilation message (stderr)

xylophone.cpp: In function 'bool Check(int, int, int, int)':
xylophone.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^
/tmp/cceTJPZg.o: In function `query(int, int)':
grader.cpp:(.text+0x0): multiple definition of `query(int, int)'
/tmp/ccjTzFuQ.o:xylophone.cpp:(.text+0xd0): first defined here
/tmp/cceTJPZg.o: In function `answer(int, int)':
grader.cpp:(.text+0x90): multiple definition of `answer(int, int)'
/tmp/ccjTzFuQ.o:xylophone.cpp:(.text+0x0): first defined here
/tmp/cceTJPZg.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccjTzFuQ.o:xylophone.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status