Submission #919514

#	Time	Username	Problem	Language	Result	Execution time	Memory
919514		Alihan_8	Xylophone (JOI18_xylophone)	C++17	0 / 100	102 ms	198812 KiB

xylophone

#include <bits/stdc++.h>

#include "xylophone.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

int d[5001][5001];

int qu(int l, int r){
    if ( d[l][r] != -1 ){
        return d[l][r];
    }
    return d[l][r] = query(l, r);
}

void solve(int N) {
    int n = N;
    memset(d, -1, sizeof(d));
    int l = 1, r = n;
    while ( l + 1 < r ){
        int md = (l + r) >> 1;
        if ( qu(md, n) != n - 1 ){
            r = md;
        } else l = md;
    }
    vector <int> A(n + 1), us(n + 1);
    A[l] = us[1] = true;
    bool f = true;
    int s = 0, lst = l;
    for ( int i = l; i < n; i++ ){
        int a = qu(i, i + 1);
        if ( A[i] + a > n || us[A[i] + a] ){
            f = false, s = -a, lst = i + 1;
        } else if ( A[i] - a <= 0 || us[A[i] - a] ){
            f = true, s = -a, lst = i + 1;
        } else{
            if ( qu(lst, i + 1) != s + a ){
                f ^= 1, s = -a, lst = i + 1;
            }
        }
        A[i + 1] = A[i] + (f ? a : -a);
        us[A[i + 1]] = true;
        s += a;
    } f = true; lst = l; s = 0;
    for ( int i = l; i > 1; i-- ){
        int a = qu(i - 1, i);
        if ( A[i] + a > n || us[A[i] + a] ){
            f = false, s = -a, lst = i - 1;
        } else if ( A[i] - a <= 0 || us[A[i] - a] ){
            f = true, s = -a, lst = i - 1;
        } else{
            if ( qu(i - 1, lst) != s + a ){
                f ^= 1, s = -a, lst = i - 1;
            }
        }
        A[i - 1] = A[i] + (f ? a : -a);
        us[A[i - 1]] = true;
        s += a;
    }
    for ( int i = 1; i <= n; i++ ){
        answer(i, A[i]);
    }
}

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