제출 #351069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351069		blue	Xylophone (JOI18_xylophone)	C++11	컴파일 에러	0 ms	0 KiB

xylophone

#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):

*/


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

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);
                }
            }
        }
    }








    assign(pos[N] - 1, N - query(pos[N] - 1, pos[N]));
    for(int i = pos[N]-2; i >= 1; 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);
                }
            }
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

xylophone.cpp: In function 'int searchN(int, int)':
xylophone.cpp:31:8: error: 'query' was not declared in this scope
   31 |     if(query(1, m) == n-1) return searchN(a, m);
      |        ^~~~~
xylophone.cpp: In function 'void assign(int, int)':
xylophone.cpp:47:5: error: 'answer' was not declared in this scope
   47 |     answer(p, a);
      |     ^~~~~~
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:60:32: error: 'query' was not declared in this scope
   60 |         assign(pos[N] + 1, N - query(pos[N], pos[N] + 1));
      |                                ^~~~~
xylophone.cpp:66:18: error: 'query' was not declared in this scope
   66 |         int X1 = query(i-1, i);
      |                  ^~~~~
xylophone.cpp:120:28: error: 'query' was not declared in this scope
  120 |     assign(pos[N] - 1, N - query(pos[N] - 1, pos[N]));
      |                            ^~~~~
xylophone.cpp: In function 'int searchN(int, int)':
xylophone.cpp:30:9: warning: control reaches end of non-void function [-Wreturn-type]
   30 |     int m = (a+b)/2;
      |         ^