Submission #231923

#	Time	Username	Problem	Language	Result	Execution time	Memory
231923		Coroian_David	Xylophone (JOI18_xylophone)	C++11	100 / 100	70 ms	540 KiB

xylophone

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

#define MAX_N 5000

using namespace std;

int A[MAX_N + 1];

#ifdef local
int query(int s, int t)
{
    int mn = 5000;
    int mx = 1;
    for(int i = s; i <= t; i ++)
    {
        mn = min(mn, A[i]);
        mx = max(mx, A[i]);
    }

    return mx - mn;
}
#endif // local

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

#ifdef local
void answer(int i, int nr)
{
    if(nr != A[i])
    {
        cout << "PE POZ " << i << " ESTE  " << A[i] << " TIU ZCICI " << nr << "\n";
        exit(0);
    }

   // cout << " PE " << i << " " << nr << " == " << A[i] << "\n";
}
#endif // local

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;

        if(poz + 2 <= n)
            baga(poz + 2, n, 1);
    }

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

        if(poz - 2 >= 1)
            baga(poz - 2, 1, -1);
    }

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

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