oj.uz

Submission #1092289

# Submission time Handle Problem Language Result Execution time Memory
1092289 2024-09-23T17:34:18 Z andro Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 344 KB 
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;

static int a[5000];
static int A[5000];
/*
int query(int l, int r) {
    int mn = 5000, mx = 0;
    for(int i = l; i <= r; i++) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    return mx - mn;
}

void answer(int index, int value) {
    A[index] = value;
}
*/
void aaa(int index, int value) {
    A[index] = value;
}

void solve(int N) {
    // answer index, value
    int l = 1, r = N, ans = - 1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(query(1, mid) == N - 1) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    aaa(ans, N);
    answer(ans, N);
    vector<int> p(N + 1, -1);
    for(int i = 1; i <= N; i++) {
        if(i == ans) {
            continue;
        }
        if(i < ans) {
            p[i] = query(i, ans);
        }
        else {
            p[i] = query(ans, i);
        }
    }
    for(int i = ans; i < N; i++) {
        if(p[i] == p[i + 1]) {
            int u = query(i, i + 1);
            // max - min = u
            // min = max - u
            aaa(i + 1, A[i] + u);
            answer(i + 1, A[i] + u);
        }
        else {
            aaa(i + 1, N - p[i + 1]);
            answer(i + 1, N - p[i + 1]);
        }
    }
    p[ans] = N;
    for(int i = ans - 1; i >= 1; i--) {
        if(p[i] == p[i + 1]) {
            int u = query(i, i + 1);
            aaa(i, A[i + 1] + u);
            answer(i, A[i + 1] + u);
        }
        else {
            aaa(i, N - p[i]);
            answer(i, N - p[i]);
        }
    }
}
/*
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    solve(n);
    cout << "\n";
    for(int i = 1; i <= n; i++) {
        cout << A[i] << " ";
    }
}*/
/*
5
2 1 5 3 4
*/

Compilation message

xylophone.cpp:5:12: warning: 'a' defined but not used [-Wunused-variable]
    5 | static int a[5000];
      |            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -