Submission #905088

# Submission time Handle Problem Language Result Execution time Memory
905088 2024-01-12T14:26:48 Z destrikes Xylophone (JOI18_xylophone) C++17
Compilation error
0 ms 0 KB
//#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
}

Compilation message

/usr/bin/ld: /tmp/ccmFXafu.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccnAEU5s.o:xylophone.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccmFXafu.o: in function `main':
grader.cpp:(.text.startup+0x30): undefined reference to `solve(int)'
collect2: error: ld returned 1 exit status