Submission #351131

#	Time	Username	Problem	Language	Result	Execution time	Memory
351131		blue	Xylophone (JOI18_xylophone)	C++11	100 / 100	87 ms	384 KiB

xylophone

#include "xylophone.h"
#include <iostream>
#include <vector>
using namespace std;


/*
13 queries to find pos(N)

1 query for pos(N)+1

For i = pos(N)+2 .. N:
    query(i-1, i)
    query(i-2, i)
    Figure out i

Do the same for i = 1..pos(1)-2

For pos(1) < i < pos(N):

*/

void debug(int y)
{
    cout << y << '\n';
}

void debug(string S)
{
    cout << S << '\n';
}

void debug(string S, int a, int b)
{
    cout << S << ' ' << a << ' ' << b << '\n';
}

// ----------------------------------------------------------------------------

int n;

int searchN(int a, int b)
{
    // debug("searchN", a, b);
    if(a == b) return a;
    int m = (a+b)/2;
    if(query(1, m) == n-1) return searchN(a, m);
    else return searchN(m+1, b);
}

vector<int> pos(5001, 0);
vector<int> A(5001, 0);

bool occ(int a)  //occupied?
{
    return (a < 1) || (n < a) || (pos[a] != 0);
}

void assign(int p, int a)
{
    pos[a] = p;
    A[p] = a;
    answer(p, a);
}

void solve(int N)
{
    // debug(111);
    n = N;
    assign( searchN(2, N), N );


    //after N
    if(pos[N] < N)
    {
        assign(pos[N] + 1, N - query(pos[N], pos[N] + 1));
    }
    // debug(555);
    for(int i = pos[N]+2; i <= N; i++)
    {
        // debug(i);
        int X1 = query(i-1, i);

        if(occ(A[i-1] + X1)) assign(i, A[i-1] - X1);
        else if(occ(A[i-1] - X1)) assign(i, A[i-1] + X1);
        else
        {
            int X2 = query(i-2, i);

            if(X2 == abs(A[i-1] - A[i-2]))
            {
                if(A[i-2] < A[i-1])
                {
                    //A[i-2] < A[i] < A[i-1]
                    assign(i, A[i-1] - X1);
                }
                else
                {
                    //A[i-1] < A[i] < A[i-2]
                    assign(i, A[i-1] + X1);
                }
            }
            else
            {
                if(A[i-2] < A[i-1] && X1 > X2)
                {
                    //A[i] < A[i-2] < A[i-1]
                    assign(i, A[i-1] - X1);
                }
                else if(A[i-2] < A[i-1] && X1 < X2)
                {
                    //A[i-2] < A[i-1] < A[i]
                    assign(i, A[i-1] + X1);
                }
                else if(A[i-1] < A[i-2] && X1 > X2)
                {
                    //A[i-1] < A[i-2] < A[i]
                    assign(i, A[i-1] + X1);
                }
                else if(A[i-1] < A[i-2] && X1 < X2)
                {
                    //A[i] < A[i-1] < A[i-2]
                    assign(i, A[i-1] - X1);
                }
                else if(A[i-1] < A[i-2] && X1 == X2)
                {
                    assign(i, A[i-1] + X1);
                }
                else// if(A[i-1] > A[i-2] && X1 == X2)
                {
                    assign(i, A[i-1] - X1);
                }
            }
        }
    }








    assign(pos[N] - 1, N - query(pos[N] - 1, pos[N]));
    for(int i = pos[N]-2; i >= 1; i--)
    {
        // debug("new i = ");
        // debug(i);

        int X1 = query(i, i+1);

        if(occ(A[i+1] + X1)) assign(i, A[i+1] - X1);
        else if(occ(A[i+1] - X1)) assign(i, A[i+1] + X1);
        else
        {
            int X2 = query(i, i+2);

            if(X2 == abs(A[i+1] - A[i+2]))
            {
                if(A[i+2] < A[i+1])
                {
                    //A[i-2] < A[i] < A[i-1]
                    assign(i, A[i+1] - X1);
                }
                else
                {
                    //A[i-1] < A[i] < A[i-2]
                    assign(i, A[i+1] + X1);
                }
            }
            else
            {
                if(A[i+2] < A[i+1] && X1 > X2)
                {
                    //A[i] < A[i-2] < A[i-1]
                    assign(i, A[i+1] - X1);
                }
                else if(A[i+2] < A[i+1] && X1 < X2)
                {
                    //A[i-2] < A[i-1] < A[i]
                    assign(i, A[i+1] + X1);
                }
                else if(A[i+1] < A[i+2] && X1 > X2)
                {
                    //A[i-1] < A[i-2] < A[i]
                    assign(i, A[i+1] + X1);
                }
                else if(A[i+1] < A[i+2] && X1 < X2)
                {
                    //A[i] < A[i-1] < A[i-2]
                    assign(i, A[i+1] - X1);
                }
                else if(A[i+1] < A[i+2] && X1 == X2)
                {
                    assign(i, A[i+1] + X1);
                }
                else// if(A[i-1] > A[i-2] && X1 == X2)
                {
                    assign(i, A[i+1] - X1);
                }
            }
        }
    }
}


//----------------------------------------------------------------------

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