Submission #846108

#	Time	Username	Problem	Language	Result	Execution time	Memory
846108		AlphaMale06	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	436 KiB

xylophone

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

void solve(int n){
    bool have[n+1]={0};
    int ans[n+1]={0};
    int mnind=n;
    int l=1; int r=n;
    while(l<=r){
        if(l==r){
            mnind=l;
            have[1]=1;
            ans[l]=1;
            break;
        }
        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, n);
        if(q1!=n-1){
            r=s;
        }
        else{
            l=s;
        }
    }
    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;
    }
    //dobro do sad?

    for(int i=mnind+2; i<=n; i++){
        int q1=query(i-1, i);
        int hi=ans[i-1]+q1;
        int lo=ans[i-1]-q1;
        if(hi>n || have[hi]){
            have[lo]=1;
            ans[i]=lo;
        }
        else if(lo<1 || have[lo]){
            have[hi]=1;
            ans[i]=hi;
        }
        else{
            int q2=query(i-2, i);
            if(q2==abs(ans[i-1]-ans[i-2])){
                if(ans[i-1]>ans[i-2])ans[i]=lo;
                else ans[i]=hi;
                have[ans[i]]=1;
            }
            else{
                if(ans[i-1]>ans[i-2]){
                    if(q1==q2){
                        ans[i]=lo;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                }
                else{
                    if(q1==q2){
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=lo;
                        have[ans[i]]=1;
                    }
                }
            }
        }
    }
    for(int i=mnind-2; i>=1; i--){
        int q1=query(i, i+1);
        int hi=ans[i+1]+q1;
        int lo = ans[i+1]-q1;
        if(hi>n || have[hi]){
            have[ans[i+1]-q1]=1;
            ans[i]=lo;
        }
        else if(lo < 1 || have[lo]){
            have[hi]=1;
            ans[i]=hi;
        }
        else{
            int q2=query(i, i+2);
            if(q2==abs(ans[i+2]-ans[i-1])){
                if(ans[i+2]>ans[i+1])ans[i]=hi;
                else ans[i]=lo;
                have[ans[i]]=1;
            }
            else{
                if(ans[i+1]>ans[i+2]){
                    if(q1==q2){
                        ans[i]=lo;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                }
                else{
                    if(q1==q2){
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=lo;
                        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