제출 #874400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874400		AlphaMale06	Xylophone (JOI18_xylophone)	C++14	100 / 100	36 ms	688 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

void solve(int n){
    bool have[n+1]={0};
    int a[n+1]={0};
    int mn;
    int l=1;
    int r=n-1;
    while(l<=r){
        int s=(l+r)/2;
        if(query(s+1, n)==n-1){
            l=s+1;
        }
        else{
            r=s-1;
        }
    }
    mn=l;
    have[1]=1;
    int nxt=1+query(mn, mn+1);
    a[mn]=1;
    a[mn+1]=nxt;
    have[nxt]=1;
    if(mn!=1){
        int prv=1+query(mn-1, mn);
        a[mn-1]=prv;
        have[prv]=1;
    }
    for(int i=mn-2; i>=1; i--){
        int q1=query(i, i+1);
        int pos1=a[i+1]+q1;
        int pos2=a[i+1]-q1;
        if(pos1<=0 || pos1>n || have[pos1]){
            a[i]=pos2;
        }
        else if(pos2<=0 || pos2>n || have[pos2]){
            a[i]=pos1;
        }
        else{
            int q2=query(i, i+2);
            if(q2==q1 || q2==abs(a[i+1]-a[i+2])){
                if(a[i+1]>a[i+2]){
                    a[i]=pos2;
                }
                else{
                    a[i]=pos1;
                }
            }
            else{
                if(a[i+1]>a[i+2]){
                    a[i]=pos1;
                }
                else a[i]=pos2;
            }
        }
        have[a[i]]=1;
    }
    for(int i=mn+2; i<n; i++){
        int q1=query(i-1, i);
        int pos1=a[i-1]+q1;
        int pos2=a[i-1]-q1;
        if(pos1<=0 || pos1>n || have[pos1]){
            a[i]=pos2;
        }
        else if(pos2<=0 || pos2>n || have[pos2]){
            a[i]=pos1;
        }
        else{
            int q2=query(i-2, i);
            if(q2==q1 || q2==abs(a[i-1]-a[i-2])){
                if(a[i-1]>a[i-2]){
                    a[i]=pos2;
                }
                else{
                    a[i]=pos1;
                }
            }
            else{
                if(a[i-1]>a[i-2]){
                    a[i]=pos1;
                }
                else a[i]=pos2;
            }
        }
        have[a[i]]=1;
    }
    for(int i=1; i<=n; i++){
        if(!have[i]){
            a[n]=i;
            break;
        }
    }
    for(int i=1; i<=n; i++){
        answer(i, a[i]);
    }
}

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