oj.uz

Submission #320513

# Submission time Handle Problem Language Result Execution time Memory
320513 2020-11-09T02:19:26 Z mohamedsobhi777 Xylophone (JOI18_xylophone) C++14
0 / 100
 2 ms 364 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 ms 364 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 ms 364 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 2 ms 364 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -