제출 #1254693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254693		random_name	Xylophone (JOI18_xylophone)	C++20	100 / 100	21 ms	724 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

static int A[5000];

void solve(int N) {
    int l = 0, r = N-1;

    while(true) {
        int m = (l + r) / 2;
        // std::cout << l << ' ' << r << '\n';
        if(query(l+1, m+1) == N-1){
            r = m;
        }

        else if(query(m+2, r+1) == N-1){
            l = m+1;
        }

        else{
            break;
        }
    }

    int li = (l+r+1) / 2;
    int ri = r;


    // std::cout << "----\n";
    while(li != ri){
        // std::cout << li << ' ' << ri << '\n';
        int m = (li + ri) / 2;
        if(query(l+1, m+1) == N-1){
            ri = m;
        }

        else{
            li = m+1;
        }
    }

    int Max = li;

    std::set<int> used;
    std::vector<int> B(N);
    B[Max] = N;
    used.insert(N);

    int temp_max = Max;
    bool accending = false;
    for(int i = Max+1; i < N; i++){
        int diff = query(i, i+1);
        if(B[i-1] + diff > N || used.count(B[i-1] + diff)){
            B[i] = B[i-1] - diff;
            used.insert(B[i]);
            continue;
        }

        if(B[i-1] - diff < 1 || used.count(B[i-1] - diff)){
            used.insert(B[i]);
            B[i] = B[i-1] + diff;
            continue;
        }

        int diff2 = query(i-1, i+1);

        if(diff2 == abs(B[i-1] - B[i-2]) || diff2 == diff){
            if(B[i-1] > B[i-2]){
                B[i] = B[i-1] - diff;
            }

            else{
                B[i] = B[i-1] + diff;
            }
            used.insert(B[i]);
            continue;
        }

        if(B[i-1] > B[i-2]){
            B[i] = B[i-1] + diff;
        }

        else{
            B[i] = B[i-1] - diff;
        }

        used.insert(B[i]);

    }


    for(int i = Max-1; i >= 0; i--){
        int diff = query(i+1, i+2);
        if(B[i+1] + diff > N || used.count(B[i+1] + diff)){
            B[i] = B[i+1] - diff;
            used.insert(B[i]);

            continue;
        }

        if(B[i+1] - diff < 1 || used.count(B[i+1] - diff)){
            B[i] = B[i+1] + diff;
            used.insert(B[i]);

            continue;
        }

        int diff2 = query(i+1, i+3);

        if(diff2 == abs(B[i+1] - B[i+2]) || diff2 == diff){
            if(B[i+1] > B[i+2]){
                B[i] = B[i+1] - diff;
            }

            else{
                B[i] = B[i+1] + diff;
            }
            used.insert(B[i]);

            continue;
        }

        if(B[i+1] > B[i+2]){
            B[i] = B[i+1] + diff;
        }

        else{
            B[i] = B[i+1] - diff;
        }

        used.insert(B[i]);


    }

    for(int i = 0; i < N; i++){
        // std::cout << B[i] << ' ';
        answer(i+1, B[i]);
    }
    // std::cout << '\n';
}

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