Submission #278241

#	Time	Username	Problem	Language	Result	Execution time	Memory
278241		Revo7	Xylophone (JOI18_xylophone)	C++14	100 / 100	71 ms	520 KiB

xylophone

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

using namespace std;
static int a[5100];
int n;
int bs(){
    int l=1,r=n,ret;
    while(l<=r){
        int mid=(l+r)/2;
        if(query(mid,n)==n-1){
            ret=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ret;
}
bool vis[5100];

bool av(int x){
    if(x>=1&&x<=n)return 1-vis[x];
    return 0;
}
void solve(int N) {
    n=N;
	int on=bs();
    //cout<<on<<endl;
    a[on]=1;
    vis[1]=1;
    a[on+1]=1+query(on,on+1);
    vis[a[on+1]]=1;
    for(int i=on;i+2<=n;i++){
        int d12=query(i+1,i+2);
        int d01=a[i+1]-a[i];
        d01=max(d01,-d01);
        if(!av(a[i+1]+d12)||!av(a[i+1]-d12)){
            if(!av(a[i+1]+d12)){
                a[i+2]=a[i+1]-d12;
                vis[a[i+2]]=1;
            }
            else{
                a[i+2]=a[i+1]+d12;
                vis[a[i+2]]=1;
            }
            continue;
        }

        int d03=query(i,i+2);
        if(d03==d01+d12){
            if(a[i+1]>a[i])a[i+2]=a[i+1]+d12;
            else a[i+2]=a[i+1]-d12;
            vis[a[i+2]]=1;
        }
        else{
            if(a[i+1]>a[i])a[i+2]=a[i+1]-d12;
            else a[i+2]=a[i+1]+d12;
            vis[a[i+2]]=1;
        }
    }

    if(on-1>=1){
        a[on-1]=a[on]+query(on-1,on);
        vis[a[on-1]]=1;
    }

    for(int i=on;i-2>=1;i--){
        int d21=query(i-2,i-1);
        if(!av(a[i-1]+d21)||!av(a[i-1]-d21)){
            if(!av(a[i-1]+d21)){
                a[i-2]=a[i-1]-d21;
            }
            else{
                a[i-2]=a[i-1]+d21;
            }
            vis[a[i-2]]=1;
            continue;
        }
        int d10=a[i-1]-a[i];
        d10=max(d10,-d10);
        int d20=query(i-2,i);
        if(d20==d21+d10){
            if(a[i-1]>a[i])a[i-2]=a[i-1]+d21;
            else a[i-2]=a[i-1]-d21;
        }
        else{
            if(a[i-1]>a[i])a[i-2]=a[i-1]-d21;
            else a[i-2]=a[i-1]+d21;
        }
        vis[a[i-2]]=1;
    }

    for(int i=1;i<=n;i++){
        answer(i,a[i]);
    }
}

Compilation message (stderr)

xylophone.cpp: In function 'int bs()':
xylophone.cpp:17:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     return ret;
      |            ^~~

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