Submission #1127962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127962		vladilius	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	408 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

void solve(int n){
    int bl = 1, br = n;
    while (bl + 1 < br){
        int m = (bl + br) / 2;
        if (query(1, m) == (n - 1)){
            br = m;
        }
        else {
            bl = m + 1;
        }
    }
    if (query(1, bl) == (n - 1)) br = bl;
    
    int p = br;
    
    vector<int> f(n + 1); f[p] = n;
    vector<bool> used(n + 1); used[n] = 1;
    
    if (p > 1){
        f[p - 1] = n - query(p - 1, p);
        used[f[p - 1]] = 1;
    }
    if (p < n){
        f[p + 1] = n - query(p, p + 1);
        used[f[p + 1]] = 1;
    }
    
    for (int i = p - 2; i > 0; i--){
        int u = query(i - 1, i);
        if (f[i + 1] <= u || used[f[i + 1] - u]){
            f[i] = f[i + 1] + u;
            used[f[i]] = 1;
            continue;
        }
        if ((f[i + 1] + u) > n || used[f[i + 1] + u]){
            f[i] = f[i + 1] - u;
            used[f[i]] = 1;
            continue;
        }

        int v = query(i, i + 2);
        if (f[i + 1] > f[i + 2]){
            f[i] = (v == (f[i + 1] + u - f[i + 2])) ? (f[i + 1] + u) : (f[i + 1] - u);
        }
        else {
            f[i] = (v == (f[i + 2] - f[i + 1] + u)) ? (f[i + 1] - u) : (f[i + 1] + u);
        }
    }
    for (int i = p + 2; i < n; i++){
        int u = query(i - 1, i);
        if (f[i - 1] <= u || used[f[i - 1] - u]){
            f[i] = f[i - 1] + u;
            used[f[i]] = 1;
            continue;
        }
        if ((f[i - 1] + u) >= n || used[f[i - 1] + i]){
            f[i] = f[i - 1] - u;
            used[f[i]] = 1;
            continue;
        }
        
        int v = query(i - 2, i);
        if (f[i - 2] > f[i - 1]){
            f[i] = (v == (f[i - 2] - f[i - 1] + u)) ? (f[i - 1] - u) : (f[i - 1] + u);
        }
        else {
            f[i] = (v == (f[i - 1] + u - f[i - 2])) ? (f[i - 1] + u) : (f[i - 1] - u);
        }
    }

    for (int i = 1; i <= n; i++){
        answer(i, f[i]);
    }
}

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