Submission #680560

#	Time	Username	Problem	Language	Result	Execution time	Memory
680560		nutella	Xylophone (JOI18_xylophone)	C++17	0 / 100	2 ms	304 KiB

xylophone

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

using namespace std;

void solve(int N) {
    vector<bool> was(N + 1);
    vector<int> A(N);

    int lo = -1, hi = N - 1;
    while (lo + 1 < hi) {
        int mid = lo + hi >> 1;
        if (query(1, mid + 1) == N - 1) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    answer(hi + 1, N);
    A[hi] = N;
    was[N] = true;

    int p = N, pp = -1;
    for (int i = hi - 1; i >= 0; --i) {
        int diff = query(i + 1, i + 2);
        int a;

        if (diff + p > N || was[diff + p]) {
            a = p - diff;
        } else if (p - diff <= 0 || was[p - diff]) {
            a = p + diff;
        } else {
            assert(pp != -1);
            int x = query(i + 1, i + 3);
            if (x == diff) {
                a = pp > p ? p + diff : p - diff;
            } else if (x == abs(pp - p)) {
                a = p + diff < pp ? p + diff : p - diff;
                assert(p < a && a < pp || pp < a && a < p);
            } else {
                a = pp > p ? pp - x : pp + x;
            }
        }

        A[i] = a;
        answer(i + 1, a);
        was[a] = true;
        pp = p;
        p = a;
    }

    for (int i = hi + 1; i < N; ++i) {
        int diff = query(i, i + 1);
        int a;

        if (diff + p > N || was[diff + p]) {
            a = p - diff;
        } else if (p - diff <= 0 || was[p - diff]) {
            a = p + diff;
        } else {
            assert(pp != -1);
            int x = query(i + 1, i + 3);
            if (x == diff) {
                a = pp > p ? p + diff : p - diff;
            } else if (x == abs(pp - p)) {
                a = p + diff < pp ? p + diff : p - diff;
                assert(p < a && a < pp || pp < a && a < p);
            } else {
                a = pp > p ? pp - x : pp + x;
            }
        }

        A[i] = a;
        answer(i + 1, a);
        was[a] = true;
        pp = p;
        p = a;
    }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:12:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |         int mid = lo + hi >> 1;
      |                   ~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from xylophone.cpp:1:
xylophone.cpp:40:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |                 assert(p < a && a < pp || pp < a && a < p);
      |                        ~~~~~~^~~~~~~~~
xylophone.cpp:68:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |                 assert(p < a && a < pp || pp < a && a < p);
      |                        ~~~~~~^~~~~~~~~

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