제출 #231921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231921		Coroian_David	Xylophone (JOI18_xylophone)	C++11	0 / 100	5 ms	256 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

#define MAX_N 5000

using namespace std;


int n;

int cautBin()
{
    int i = 0;
    int pas = 1 << 12;
    while(pas != 0)
    {
        if(i + pas < n && query(1, i + pas) != n - 1)
            i += pas;

        pas >>= 1;
    }

    return i + 1;
}

int v[MAX_N + 1];
int diff[MAX_N + 1];
int ap[MAX_N + 1];

void baga(int st, int dr, int pas)
{
    for(int i = st; i != dr + pas; i += pas)
    {
        int sign = 0;
        int x = (i - pas < i ? query(i - pas, i) : query(i, i - pas));

        if(v[i - pas] + x >= n || ap[v[i - pas] + x] == 1)
            sign = -1;

        else
            if(v[i - pas] - x < 1 || ap[v[i - pas] - x] == 1)
                sign = 1;

        else
        {
            int y = (i - 2*pas < i ? query(i - 2*pas, i) : query(i, i - 2*pas));

            if(y == diff[i - pas])
                sign = (v[i - 2*pas] < v[i - pas] ? -1 : 1);

            else
                if(y == x + diff[i - pas])
                    sign = (v[i - pas] < v[i - 2*pas] ? -1 : 1);

            else if(y == x)
                sign = (v[i - pas] > v[i - 2*pas] ? -1 : 1);
        }

        diff[i] = x;
        v[i] = v[i - pas] + x * sign;
        ap[v[i]] = 1;
    }
}



void solve(int N)
{
    n = N;
    int poz = cautBin();

    v[poz] = n;
    ap[v[poz]] = 1;

    if(poz + 1 <= n)
    {
        v[poz + 1] = n - query(poz, poz + 1);
        diff[poz + 1] = v[poz] - v[poz + 1];
        ap[v[poz + 1]] = 1;

        baga(poz + 2, n, 1);
    }

    if(poz - 1 >= 1)
    {
        v[poz - 1] = n - query(poz, poz - 1);
        diff[poz - 1] = v[poz] - v[poz - 1];
        ap[v[poz - 1]] = 1;

        baga(poz - 2, 1, -1);
    }

    for(int i = 1; i <= n; i ++)
        answer(i, v[i]);
}

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