Submission #924779

#	Time	Username	Problem	Language	Result	Execution time	Memory
924779		boris_mihov	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	344 KiB

xylophone

#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
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53