Submission #141056

#	Time	Username	Problem	Language	Result	Execution time	Memory
141056		meatrow	Xylophone (JOI18_xylophone)	C++17	47 / 100	114 ms	444 KiB

xylophone

//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

using ll = long long;
using ld = long double;

const int N = 5000;

int a[N];
int b[N];
/*
int query(int l, int r) {
    return *max_element(b + l - 1, b + r) - *min_element(b + l - 1, b + r);
}
*/
void solve(int n) {
    int l = 1, r = n;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        int t = query(1, mid);
        if (t == n - 1) {
            r = mid;
        } else {
            l = mid;
        }
    }
    a[r] = n;
    for (int i = r + 1; i <= n; i++) {
        int t = query(i - 1, i);
        if (a[i - 1] + t >= n) {
            a[i] = a[i - 1] - t;
            continue;
        }
        if (a[i - 1] - t < 1) {
            a[i] = a[i - 1] + t;
            continue;
        }
        int u = query(i - 2, i);
        if (u == abs(a[i - 2] - a[i - 1])) {
            if (a[i - 2] < a[i - 1]) {
                a[i] = a[i - 1] - t;
            } else {
                a[i] = a[i - 1] + t;
            }
            continue;
        }
        if (u != t) {
            int cand = a[i - 2] + u;
            if (cand == a[i - 1] - t || cand == a[i - 1] + t) {
                a[i] = cand;
            } else {
                a[i] = cand - 2 * u;
            }
            continue;
        }
        if (a[i - 2] < a[i - 1]) {
            a[i] = a[i - 1] - t;
        } else {
            a[i] = a[i - 1] + t;
        }
    }
    for (int i = r - 1; i >= 1; i--) {
        int t = query(i, i + 1);
        if (a[i + 1] + t >= n) {
            a[i] = a[i + 1] - t;
            continue;
        }
        if (a[i + 1] - t < 1) {
            a[i] = a[i + 1] + t;
            continue;
        }
        int u = query(i, i + 2);
        if (u == abs(a[i + 2] - a[i + 1])) {
            if (a[i + 2] < a[i + 1]) {
                a[i] = a[i + 1] - t;
            } else {
                a[i] = a[i + 1] + t;
            }
            continue;
        }
        if (u != t) {
            int cand = a[i + 2] + u;
            if (cand == a[i + 1] - t || cand == a[i + 1] + t) {
                a[i] = cand;
            } else {
                a[i] = cand - 2 * u;
            }
            continue;
        }
        if (a[i + 2] < a[i + 1]) {
            a[i] = a[i + 1] - t;
        } else {
            a[i] = a[i + 1] + t;
        }
    }
    for (int i = 1; i <= n; i++) {
        answer(i, a[i]);
    }
}

/*int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    iota(b, b + n, 1);
    random_shuffle(b, b + n);
    for (int i = 0; i < n; i++) {
        cout << b[i] << " \n"[i + 1 == n];
    }
    solve(n);
    return 0;
}*/

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