Submission #1105287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105287		Zero_OP	Xylophone (JOI18_xylophone)	C++17	100 / 100	70 ms	98632 KiB

xylophone

#include <bits/stdc++.h>
#ifndef LOCAL
    #include <xylophone.h>
#endif // LOCAL

using namespace std;

const int MAX = 5e3 + 5;

#ifdef LOCAL
int A[MAX];

int query(int s, int t){
    return *max_element(A + s, A + t + 1) - *min_element(A + s, A + t + 1);
}

void answer(int i, int a){
//    cout << i << " : " << a << '\n';
    if(A[i] != a){
        cout << "WRONG ANSWER\n";
        exit(0);
    }
}
#endif

int memo[MAX][MAX];

int ask(int l, int r){
    assert(l <= r);
    if(l == r) return 0;
    if(memo[l][r] != 0) return memo[l][r];
    return memo[l][r] = query(l, r);
}

void solve(int N){
    memset(memo, 0, sizeof(memo));
    if(N == 1){
        answer(1, 1);
        answer(2, 2);
        return;
    }
    int l = 1, r = N, R = -1;
    while(l <= r){
        int mid = l + r >> 1;
        if(ask(1, mid) == N - 1) R = mid, r = mid - 1;
        else l = mid + 1;
    }

    l = 1, r = R - 1;
    int L = 1;
    while(l <= r){
        int mid = l + r >> 1;
        if(ask(mid, R) == N - 1) L = mid, l = mid + 1;
        else r = mid - 1;
    }

    //find L, R that A[L] = 1, A[R] = N
    vector<int> a(N + 1);
    a[L] = 1;
    a[R] = N;

    if(L > 1) a[L - 1] = 1 + ask(L - 1, L);
    if(R < N) a[R + 1] = N - ask(R, R + 1);

    vector<bool> used(N + 1);
    used[1] = used[N] = true;

    auto casework = [&](int x, int y, int nextTwo, int nextThree){
        int case1 = x - nextTwo;
        if(max({case1, x, y}) - min({case1, x, y}) == nextThree) return case1;

        int case2 = x + nextTwo;
        if(max({case2, x, y}) - min({case2, x, y}) == nextThree) return case2;

        cout << x << ' ' << y << ' ' << nextTwo << ' ' << nextThree << '\n';
        assert(false);
    };

    for(int i = L - 2; i >= 1; --i){
        int delta = ask(i, i + 1);
        if(a[i + 1] - delta < 0 || used[a[i + 1] - delta]) a[i] = a[i + 1] + delta;
        else if(a[i + 1] + delta > N || used[a[i + 1] + delta]) a[i] = a[i + 1] - delta;
        else a[i] = casework(a[i + 1], a[i + 2], delta, ask(i, i + 2));

        used[a[i]] = true;
    }

    for(int i = R + 2; i <= N; ++i){
        int delta = ask(i - 1, i);
        if(a[i - 1] - delta < 0 || used[a[i - 1] - delta]) a[i] = a[i - 1] + delta;
        else if(a[i - 1] + delta > N || used[a[i - 1] + delta]) a[i] = a[i - 1] - delta;
        else a[i] = casework(a[i - 1], a[i - 2], delta, ask(i - 2, i));

        used[a[i]] = true;
    }

    if(L + 1 < R){
        a[L + 1] = 1 + ask(L, L + 1);
        for(int i = L + 2; i < R; ++i){
            int delta = ask(i - 1, i);
            if(a[i - 1] - delta < 0 || used[a[i - 1] - delta]) a[i] = a[i - 1] + delta;
            else if(a[i - 1] + delta > N || used[a[i - 1] + delta]) a[i] = a[i - 1] - delta;
            else a[i] = casework(a[i - 1], a[i - 2], delta, ask(i - 2, i));

            used[a[i]] = true;
        }
    }

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

#ifdef LOCAL
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }

int main(){
    srand(time(nullptr));

    for(int itest = 1; itest <= 300; ++itest){
        int N = random(2, 30);
        iota(A + 1, A + 1 + N, 1);
        shuffle(A + 1, A + 1 + N, rng);

//        int N = 6;
//        vector<int> vec = {1, 6, 5, 3, 2, 4};
//        copy(vec.begin(), vec.end(), A + 1);

        int pos1 = -1, posN = -1;
        for(int i = 1; i <= N; ++i){
            if(A[i] == 1) pos1 = i;
            if(A[i] == N) posN = i;
        }

        if(pos1 > posN){
            swap(pos1, posN);
            swap(A[pos1], A[posN]);
        }

        cout << "The permutation length N : ";
        for(int i = 1; i <= N; ++i) cout << A[i] << ' '; cout << '\n';
        solve(N);
        cout << "Passed\n";
    }

    return 0;
}
#endif // LOCAL

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~
xylophone.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~

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