Submission #1286494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286494		StefanSebez	Xylophone (JOI18_xylophone)	C++20	100 / 100	19 ms	452 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const int N=5050,inf=1e9;
int a[N];
void solve(int n){
    int l=1,r=n,idx=0;
    while(l<=r){
        int mid=l+r>>1;
        if(query(mid,n)==n-1){l=mid+1;idx=mid;}
        else r=mid-1;
    }
    bool was[n+10]={false};
    a[idx]=1;was[1]=true;
    int d[n+10];
    for(int i=1;i<n;i++) d[i]=query(i,i+1);
    if(idx+1<=n) a[idx+1]=1+d[idx],was[a[idx+1]]=true;
    if(idx-1>=1) a[idx-1]=a[idx]+d[idx-1],was[a[idx-1]]=true;
    for(int i=idx+2;i<=n;i++){
        if(!(1<=a[i-1]+d[i-1]&&a[i-1]+d[i-1]<=n)||was[a[i-1]+d[i-1]]) a[i]=a[i-1]-d[i-1];
        else if(!(1<=a[i-1]-d[i-1]&&a[i-1]-d[i-1]<=n)||was[a[i-1]-d[i-1]]) a[i]=a[i-1]+d[i-1];
        else{
            int x=query(i-2,i);
            if(x==d[i-1]||x==d[i-2]){
                if(a[i-2]>a[i-1]) a[i]=a[i-1]+d[i-1];
                else a[i]=a[i-1]-d[i-1];
            }
            else{
                if(a[i-2]<a[i-1]) a[i]=a[i-1]+d[i-1];
                else a[i]=a[i-1]-d[i-1];
            }
        }
        was[a[i]]=true;
    }
    for(int i=idx-2;i>=1;i--){
        if(!(1<=a[i+1]+d[i]&&a[i+1]+d[i]<=n)||was[a[i+1]+d[i]]) a[i]=a[i+1]-d[i];
        else if(!(1<=a[i+1]-d[i]&&a[i+1]-d[i]<=n)||was[a[i+1]-d[i]]) a[i]=a[i+1]+d[i];
        else{
            int x=query(i,i+2);
            if(x==d[i+1]||x==d[i]){
                if(a[i+2]>a[i+1]) a[i]=a[i+1]+d[i];
                else a[i]=a[i+1]-d[i];
            }
            else{
                if(a[i+2]<a[i+1]) a[i]=a[i+1]+d[i];
                else a[i]=a[i+1]-d[i];
            }
        }
        was[a[i]]=true;
    }
    for(int i=1;i<=n;i++) answer(i,a[i]);
}

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