Submission #709565

#	Time	Username	Problem	Language	Result	Execution time	Memory
709565		ToroTN	Xylophone (JOI18_xylophone)	C++14	100 / 100	119 ms	500 KiB

xylophone

#include<bits/stdc++.h>
using namespace std;
#include "xylophone.h"
//#include "grader.cpp"
//static int A[5000];

int n,dis[5005][2],arr[5005],flip[5005],mn,mx,idx_mn,idx_mx;
void solve(int N) 
{
    n=N;
	for(int i=1;i<=n;i++) 
    {
        if(i+1<=n)dis[i][0]=query(i,i+1);
        if(i+2<=n)dis[i][1]=query(i,i+2);
	}
    /*for(int i=1;i<n;i++)printf("%d ",dis[i][0]);
    printf("\n");
    for(int i=1;i<n-1;i++)printf("%d ",dis[i][1]);
    printf("\n");*/
    arr[1]=0;
    arr[2]=dis[1][0];
    for(int i=2;i<n;i++)
    {
        if(dis[i-1][1]==dis[i-1][0]+dis[i][0])
        {
            if(arr[i]>arr[i-1])
            {
                arr[i+1]=arr[i]+dis[i][0];
            }else
            {
                arr[i+1]=arr[i]-dis[i][0];
            }
        }else if(dis[i-1][0]==dis[i-1][1])
        {
            if(arr[i]>arr[i-1])
            {
                arr[i+1]=arr[i]-dis[i][0];
            }else
            {
                arr[i+1]=arr[i]+dis[i][0];
            }
        }else
        {
            if(arr[i]>arr[i-1])
            {
                arr[i+1]=arr[i]-dis[i][0];
            }else
            {
                arr[i+1]=arr[i]+dis[i][0];
            }
        }
    }
    for(int i=1;i<=n;i++)flip[i]=-arr[i];
    mn=1e9;
    mx=-1e9;
    for(int i=1;i<=n;i++)
    {
        if(arr[i]>mx)
        {
            mx=arr[i],idx_mx=i;
        }
        if(arr[i]<mn)
        {
            mn=arr[i],idx_mn=i;
        }
    }
    if(idx_mn<idx_mx)
    {
        for(int i=1;i<=n;i++)
        {
            answer(i,arr[i]+1-mn);
        }
    }else
    {
        mn=1e9;
        mx=-1e9;
        for(int i=1;i<=n;i++)
        {
            if(flip[i]>mx)
            {
                mx=flip[i],idx_mx=i;
            }
            if(flip[i]<mn)
            {
                mn=flip[i],idx_mn=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            answer(i,flip[i]+1-mn);
        }
    }
}

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