oj.uz

Submission #1091720

# Submission time Handle Problem Language Result Execution time Memory
1091720 2024-09-21T23:05:20 Z raphaelp Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 344 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
/*vector<int> Tab;
int query(int a, int b)
{
    a--, b--;
    int minn = Tab.size(), maxx = 0;
    for (int i = a; i <= b; i++)
    {
        minn = min(minn, Tab[i]);
        maxx = max(maxx, Tab[i]);
    }
    return maxx - minn;
}
void answer(int i, int val) { cout << val << ' '; }*/
void solve(int N)
{
    int L = 0, R = N;
    while (L != R)
    {
        int m = (L + R) / 2;
        int temp = query(m + 1, N);
        if (temp == N - 1)
            L = m + 1;
        else
            R = m;
    }
    int ref = L - 1;
    vector<int> ans(N, -1), occ(N);
    occ[0] = 1;
    ans[ref] = 0;
    for (int i = ref + 1; i < N; i++)
    {
        int temp = query(i, i + 1);
        if (ans[i - 1] + temp >= N || occ[ans[i - 1] + temp])
            ans[i] = ans[i - 1] - temp;
        else if (ans[i - 1] - temp < 0 || occ[ans[i - 1] - temp])
            ans[i] = ans[i - 1] + temp;
        else
        {
            int temp2 = query(i - 1, i + 1);
            if (temp2 == max(0, ans[i - 1] - ans[i - 2]) + temp)
                ans[i] = ans[i - 1] + temp;
            else
                ans[i] = ans[i - 1] - temp;
        }
        occ[ans[i]] = 1;
    }
    for (int i = ref - 1; i >= 0; i--)
    {
        int temp = query(i + 1, i + 2);
        if (ans[i + 1] + temp >= N || occ[ans[i + 1] + temp])
            ans[i] = ans[i + 1] - temp;
        else if (ans[i + 1] - temp < 0 || occ[ans[i + 1] - temp])
            ans[i] = ans[i + 1] + temp;
        else
        {
            int temp2 = query(i + 1, i + 3);
            if (temp2 == max(0, ans[i + 1] - ans[i + 2]) + temp)
                ans[i] = ans[i + 1] + temp;
            else
                ans[i] = ans[i + 1] - temp;
        }
        occ[ans[i]] = 1;
    }
    for (int i = 0; i < N; i++)
        answer(i + 1, ans[i] + 1);
}
/*int main()
{
    int N;
    cin >> N;
    Tab.assign(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
    }
    solve(N);
}*/

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 -