Submission #320513

#	Time	Username	Problem	Language	Result	Execution time	Memory
320513		mohamedsobhi777	Xylophone (JOI18_xylophone)	C++14	0 / 100	2 ms	364 KiB

xylophone

#include "xylophone.h"

using namespace std;

int n;

int a1, an;

void dac(int l, int r)
{
        if (l + 1 == r)
        {
                a1 = l;
                an = r;
                return;
        }
        int mid = (l + r) >> 1;
        if (query(l, mid) == n - 1)
        {
                dac(l, mid);
        }
        else if (query(mid + 1, r) == n - 1)
        {
                dac(mid + 1, r);
        }
        else
        {

                int L = l, R = mid - 1;
                while (L <= R)
                {
                        int m = (L + R) >> 1;
                        if (query(m, r) == n - 1)
                        {
                                a1 = m;
                                L = m + 1;
                        }
                        else
                                R = m - 1;
                }
                L = mid + 1, R = r;
                while (L <= R)
                {
                        int m = (L + R) >> 1;
                        if (query(l, m) == n - 1)
                        {
                                an = m;
                                R = m - 1;
                        }
                        else
                                L = m + 1;
                }
                return;
        }
}

int arr[10000];
int vis[10000];

void conLhs()
{
        int Max = 0;
        int pMax = 0;
        int Min = 1e9;
        int pMin = 0;
        for (int i = a1 - 1; i; --i)
        {
                int q = query(i, a1);
                if (vis[q + 1])
                {
                        int q2 = query(i, pMax);
                        if (q2 == query(i + 1, pMax))
                        {
                                arr[i] = query(i, pMin) + arr[pMin];
                        }
                        else
                                arr[i] = Max - q2;
                }
                else
                        arr[i] = q + 1;
                ++vis[arr[i]];
                if (arr[i] > Max)
                {
                        Max = arr[i];
                        pMax = i;
                        Min = 1e9;
                }
                if (arr[i] < Min)
                {
                        Min = arr[i];
                        pMin = i;
                }
        }
}

void conMhs()
{
        int Max = 0;
        int pMax = 0;
        int Min = 1e9;
        int pMin = 0;
        for (int i = a1 + 1; i < an; ++i)
        {
                int q = query(a1, i);
                if (vis[q + 1])
                {
                        int q2 = query(pMax, i);
                        if (q2 == query(pMax, i - 1))
                        {
                                arr[i] = query(pMin, i) + arr[pMin];
                        }
                        else
                                arr[i] = Max - q2;
                }
                else
                        arr[i] = q + 1;
                ++vis[arr[i]];
                if (arr[i] > Max)
                {
                        Max = arr[i];
                        pMax = i;
                        Min = 1e9;
                }
                if (arr[i] < Min)
                {
                        Min = arr[i];
                        pMin = i;
                }
        }
}

void conRhs()
{
        int Max = 0;
        int pMax = 0;
        int Min = 1e9;
        int pMin = 0;
        for (int i = an + 1; i <= n; ++i)
        {
                int q = query(an, i);
                if (vis[n - q])
                {
                        int q2 = query(pMin, i);
                        if (q2 == query(pMin, i - 1))
                        {
                                arr[i] = Max - query(pMax, i);
                        }
                        else
                                arr[i] = Min + q2;
                }
                else
                        arr[i] = n - q;
                ++vis[arr[i]];

                if (arr[i] < Min)
                {
                        Min = arr[i];
                        pMin = i;
                        Max = 0;
                }
                if (arr[i] > Max)
                {
                        Max = arr[i];
                        pMax = i;
                }
        }
}

void solve(int N)
{
        n = N;
        dac(1, N);
        arr[a1] = 1;
        arr[an] = N;
        conLhs();
        conMhs();
        conRhs();
        for (int i = 1; i <= N; ++i)
        {
                answer(i, arr[i]);
//                printf("%d ", arr[i]);
        }
}

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