oj.uz

Submission #924779

# Submission time Handle Problem Language Result Execution time Memory
924779 2024-02-09T16:26:54 Z boris_mihov Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 344 KB 
#include "xylophone.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <chrono>
#include <random>

typedef long long llong;
const int MAXN = 5000 + 10;

int a[MAXN];
void solve(int n) 
{
    int l = 1, r = n, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (query(1, mid) < n - 1) l = mid;
        else r = mid;
    }

    a[r] = n;
    int idx = r;
    int last = 0;
    bool isMAX = true;
    for (int pos = r + 1 ; pos <= n ; ++pos)
    {
        int curr = query(idx, pos);
        if (curr == last)
        {
            pos--;
            isMAX ^= 1;
            idx = pos;
            continue;
        }

        if (isMAX)
        {
            a[pos] = a[idx] - curr;
        } else
        {
            a[pos] = a[idx] + curr;
        }
        
        last = curr;
    }

    idx = r;
    last = 0;
    isMAX = true;
    for (int pos = r - 1 ; pos >= 1 ; --pos)
    {
        int curr = query(pos, idx);
        if (curr == last)
        {
            pos++;
            isMAX ^= 1;
            idx = pos;
            continue;
        }

        if (isMAX)
        {
            a[pos] = a[idx] - curr;
        } else
        {
            a[pos] = a[idx] + curr;
        }

        last = curr;
    }

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

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 1 ms 344 KB Wrong Answer [7]
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 1 ms 344 KB Wrong Answer [7]
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 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -