제출 #924787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924787		boris_mihov	Xylophone (JOI18_xylophone)	C++17	100 / 100	54 ms	1104 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];
bool isTaken[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;
    if (r > 1) 
    {
        a[r - 1] = a[r] - query(r - 1, r);
        isTaken[a[r - 1]] = true;
    }
    if (r < n) 
    {
        a[r + 1] = a[r] - query(r, r + 1);
        isTaken[a[r + 1]] = true;
    }

    isTaken[a[r]] = true;
    for (int pos = r + 2 ; pos <= n ; ++pos)
    {
        int curr = query(pos - 1, pos);
        if (a[pos - 1] - curr <= 0 || isTaken[a[pos - 1] - curr])
        {
            a[pos] = a[pos - 1] + curr;
            continue;
        }

        if (a[pos - 1] - curr > n || isTaken[a[pos - 1] + curr])
        {
            a[pos] = a[pos - 1] - curr;
            continue;
        }
        
        int all = query(pos - 2, pos);
        if ((all == curr + abs(a[pos - 1] - a[pos - 2])) ^ (a[pos - 2] > a[pos - 1]))
        {
            a[pos] = a[pos - 1] + curr;
        } else
        {
            a[pos] = a[pos - 1] - curr;
        }

        isTaken[a[pos]] = true;
    }

    for (int pos = r - 2 ; pos >= 1 ; --pos)
    {
        int curr = query(pos, pos + 1);
        if (a[pos + 1] - curr <= 0 || isTaken[a[pos + 1] - curr])
        {
            a[pos] = a[pos + 1] + curr;
            continue;
        }

        if (a[pos + 1] - curr > n || isTaken[a[pos + 1] + curr])
        {
            a[pos] = a[pos + 1] - curr;
            continue;
        }
        
        int all = query(pos, pos + 2);
        if ((all == curr + abs(a[pos + 1] - a[pos + 2])) ^ (a[pos + 2] > a[pos + 1]))
        {
            a[pos] = a[pos + 1] + curr;
        } else
        {
            a[pos] = a[pos + 1] - curr;
        }

        isTaken[a[pos]] = true;
    }

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

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53