Submission #931935

#	Time	Username	Problem	Language	Result	Execution time	Memory
931935		a_l_i_r_e_z_a	Xylophone (JOI18_xylophone)	C++17	100 / 100	56 ms	1720 KiB

xylophone

// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
#include "xylophone.h";
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 10000 + 5;
const int inf = 1e9 + 7, mod = 1e9 + 7;
int n, a[maxn], b[maxn];
bool mark[maxn];

void solve(int N){
    n = N;
    for(int i = 1; i <= n - 1; i++) b[i] = query(i, i + 1);
    int l = 1, r = n + 1;
    while(r - l > 1){
        int mid = (l + r) / 2;
        if(query(1, mid) == n - 1) r = mid;
        else l = mid;
    }
    int psn = r;
    mark[n] = 1;
    mark[n - b[psn - 1]] = 1;
    a[psn] = n;
    a[psn - 1] = n - b[psn - 1];
    if(psn < n){
        a[psn + 1] = n - b[psn];
        mark[n - b[psn]] = 1;
    }
    for(int i = psn + 2; i <= n; i++){
        if(mark[a[i - 1] + b[i - 1]]){
            a[i] = a[i - 1] - b[i - 1];
            mark[a[i - 1] - b[i - 1]] = 1;
            continue;
        }
        else if(a[i - 1] - b[i - 1] >= 1 && mark[a[i - 1] - b[i - 1]]){
            a[i] = a[i - 1] + b[i - 1];
            mark[a[i - 1] + b[i - 1]] = 1;
            continue;
        }
        int x = query(i - 2, i);
        int mn = min(a[i - 2], a[i - 1]);
        int mx = a[i - 2] + a[i - 1] - mn;
        if(max(mx, a[i - 1] + b[i - 1]) - mn == x){
            a[i] = a[i - 1] + b[i - 1];
            mark[a[i - 1] + b[i - 1]] = 1;
        }
        else{
            a[i] = a[i - 1] - b[i - 1];
            mark[a[i - 1] - b[i - 1]] = 1;
        }
    }
    for(int i = psn - 2; i >= 1; i--){
        if(mark[a[i + 1] + b[i]]){
            a[i] = a[i + 1] - b[i];
            mark[a[i + 1] - b[i]] = 1;
            continue;
        }
        else if(a[i + 1] - b[i] >= 1 && mark[a[i + 1] - b[i]]){
            a[i] = a[i + 1] + b[i];
            mark[a[i + 1] + b[i]] = 1;
            continue;
        }
        int x = query(i, i + 2);
        int mn = min(a[i + 2], a[i + 1]);
        int mx = a[i + 2] + a[i + 1] - mn;
        if(max(mx, a[i + 1] + b[i]) - mn == x){
            a[i] = a[i + 1] + b[i];
            mark[a[i + 1] + b[i]] = 1;
        }
        else{
            a[i] = a[i + 1] - b[i];
            mark[a[i + 1] - b[i]] = 1;
        }
    }
    for(int i = 1; i <= n; i++) answer(i, a[i]);
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     return 0;
// }

Compilation message (stderr)

xylophone.cpp:5:23: warning: extra tokens at end of #include directive
    5 | #include "xylophone.h";
      |                       ^

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53