oj.uz

Submission #919514

# Submission time Handle Problem Language Result Execution time Memory
919514 2024-02-01T03:59:32 Z Alihan_8 Xylophone (JOI18_xylophone) C++17
0 / 100
 102 ms 198812 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 98136 KB Output is correct
2 Correct 15 ms 98136 KB Output is correct
3 Runtime error 102 ms 198812 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 98136 KB Output is correct
2 Correct 15 ms 98136 KB Output is correct
3 Runtime error 102 ms 198812 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 98136 KB Output is correct
2 Correct 15 ms 98136 KB Output is correct
3 Runtime error 102 ms 198812 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -