제출 #845936

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

xylophone

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

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

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