Submission #1175427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175427		adkjt	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	452 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
//static int A[5000];
int diff[5555],trend[5555],dir[5555],ans[5555];

void solve(int n)
{

    for(int i=1; i<=n-1; i++)
        diff[i]=query(i,i+1);
    for(int i=1; i<=n-2; i++)
        trend[i]=query(i,i+2);

    dir[1]=1;
    for(int i=1; i<=n-2; i++)
    {
        if(trend[i]==diff[i]+diff[i+1])
            dir[i+1]=dir[i];
        else
            dir[i+1]=dir[i]*-1;
    }
    int mn=1,mx=n;
    ans[1]=1;
    for(int i=1; i<n; i++)
        ans[i+1]=diff[i]*dir[i]+ans[i],mn=min(mn,ans[i+1]),mx=max(mx,ans[i+1]);
    //for(int i=1; i<=n; i++)cout<<ans[i]<<' ';
    if(mn<1)
    {
        for(int i=1; i<=n; i++)
            ans[i]+=(1-mn);
    }
    else
        for(int i=1; i<=n; i++)
            ans[i]-=mx-n;

    int idx1,idxn;
    for(int i=1; i<=n; i++)
    {
        if(ans[i]==1) idx1=i;
        if(ans[i]==n) idxn=i;
    }
    if(idx1>idxn)
    {
        for(int i=1; i<=n-1; i++) dir[i]*=-1;
        int mn=1,mx=n;
        ans[1]=1;
        for(int i=1; i<n; i++)
            ans[i+1]=diff[i]*dir[i]+ans[i],mn=min(mn,ans[i+1]),mx=max(mx,ans[i+1]);
        //for(int i=1; i<=n; i++)cout<<ans[i]<<' ';
        if(mn<1)
        {
            for(int i=1; i<=n; i++)
                ans[i]+=(1-mn);
        }
        else
            for(int i=1; i<=n; i++)
                ans[i]-=mx-n;
        //reverse(ans+1,ans+1+n);
    }
//for(int i=1; i<=n; i++)cout<<ans[i]<<' ';
    for(int i=1; i<=n; i++)
        answer(i,ans[i]);
}

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