Submission #874372

#	Time	Username	Problem	Language	Result	Execution time	Memory
874372		AlphaMale06	Xylophone (JOI18_xylophone)	C++14	47 / 100	45 ms	448 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;
            }
        }
    }
    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;
            }
        }
    }
    for(int i=1; i<=n; i++){
        answer(i, a[i]);
    }
}

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