Submission #232827

#	Time	Username	Problem	Language	Result	Execution time	Memory
232827		Charis02	Xylophone (JOI18_xylophone)	C++14	0 / 100	5 ms	512 KiB

xylophone

#include "xylophone.h"
#include<iostream>

using namespace std;

int A[5001];
bool used[5001];
int NN;

bool is_valid(int x)
{
    return (1 <= x && x<=NN && !used[x]);
}

void solve(int N)
{
    NN=N;
    int low = 1;
    int high = N-1;
    int res = 1;

    while(low <= high)
    {
        int mid = (low+high)/2;

        if(query(mid,N) == N-1)
        {
            res=max(res,mid);
            low=mid+1;
        }
        else
            high=mid-1;
    }

    used[1] = true;
    A[res] = 1;

    for(int i = res-1;i >= 1;i --)
    {
        int dif1 = query(i,i+1);

        if(!is_valid(A[i+1]+dif1))
            A[i] = A[i+1]-dif1;
        else if(!is_valid(A[i+1]-dif1))
            A[i] = A[i+1]+dif1;
        else
        {
            int dif2 = query(i,i+2);

            if(A[i+1] < A[i+2])
            {
                if(dif2 == A[i+2]-A[i+1])
                    A[i] = dif1+A[i+1];
                else if(dif2 > dif1)
                    A[i] = dif1+A[i+1];
                else
                    A[i] = A[i+1]-dif1;
            }
            else
            {
                if(dif2 == A[i+1]-A[i+2])
                    A[i] = A[i+1]-dif1;
                else if(dif2 > dif1)
                    A[i] = A[i+1]+dif1;
                else
                    A[i] = A[i+1]-dif1;
            }
        }

        used[A[i]] = true;
    }

    for(int i = res+1;i <= N;i++)
    {
        int dif1 = query(i-1,i);

        if(!is_valid(A[i-1]+dif1))
            A[i] = A[i-1]-dif1;
        else if(!is_valid(A[i-1]-dif1))
            A[i] = A[i-1]+dif1;
        else
        {
            int dif2 = query(i-2,i);

            if(A[i-1] < A[i-2])
            {
                if(dif2 == A[i-2]-A[i-1])
                    A[i] = dif1+A[i-1];
                else if(dif2 > dif1)
                    A[i] = dif1+A[i-1];
                else
                    A[i] = A[i-1]-dif1;
            }
            else
            {
                if(dif2 == A[i-1]-A[i-2])
                    A[i] = A[i-1]-dif1;
                else if(dif2 > dif1)
                    A[i] = A[i-1]+dif1;
                else
                    A[i] = A[i-1]-dif1;
            }
        }

        used[A[i]] = true;
    }

    for(int i = 1;i <= N;i++)
        answer(i,A[i]);
    return;
}

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