Submission #1032526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032526		vjudge1	Xylophone (JOI18_xylophone)	C++17	47 / 100	61 ms	20820 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
static int A[5000];
int sv[5010][5010],CC=0;
int myqry(int l,int r){
    if(l>r)swap(l,r);
    if(l==r)return 0;
    if(sv[l][r])return sv[l][r];
    assert(++CC<10000);
    return sv[l][r]=query(l,r);
}
int ans[5010];
int makesense(int a,int b,int c,int ac){
    return ac==max({a,b,c})-min({a,b,c});
}

void solve(int N) {
    int l=1,r=N-1,res=0;
    while(l<=r){
        int mid=l+r>>1;
        if(myqry(mid,N)==N-1)
            res=mid,l=mid+1;
        else r=mid-1;
    }
    int posof1=res;
    ans[posof1]=1;
    if(posof1>1)
        ans[posof1-1]=myqry(posof1-1,posof1)+1;
    ans[posof1+1]=myqry(posof1,posof1+1)+1;
    for(int i=posof1-2;i>0;i--){
        int k=myqry(i,i+1);
        if(ans[i+1]-k<1)
            ans[i]=ans[i+1]+k;
        else if(ans[i+1]+k>N)
            ans[i]=ans[i+1]-k;
        else {
            int c=query(i,i+2);
            if(makesense(ans[i+1]-k,ans[i+1],ans[i+2],c))
                ans[i]=ans[i+1]-k;
            else ans[i]=ans[i+1]+k;
        }
    }
    for(int i=posof1+2;i<=N;i++){
        int k=myqry(i-1,i);
        if(ans[i-1]-k<1)
            ans[i]=ans[i-1]+k;
        else if(ans[i+1]+k>N)
            ans[i]=ans[i-1]-k;
        else {
            int c=query(i-2,i);
            if(makesense(ans[i-1]-k,ans[i-1],ans[i-2],c))
                ans[i]=ans[i-1]-k;
            else ans[i]=ans[i-1]+k;
        }
    }
    for(int i=1;i<=N;i++)
        answer(i,ans[i]);
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid=l+r>>1;
      |                 ~^~
xylophone.cpp: At global scope:
xylophone.cpp:4:12: warning: 'A' defined but not used [-Wunused-variable]
    4 | static int A[5000];
      |            ^

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