Submission #680563

#	Time	Username	Problem	Language	Result	Execution time	Memory
680563		nutella	Xylophone (JOI18_xylophone)	C++17	100 / 100	71 ms	300 KiB

xylophone

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

using namespace std;

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

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

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

    p = N;
    pp = -1;
    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 + 1);
            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;
            }
        }

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

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:11:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |         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:38:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |                 assert(p < a && a < pp || pp < a && a < p);
      |                        ~~~~~~^~~~~~~~~
xylophone.cpp:67:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   67 |                 assert(p < a && a < pp || pp < a && a < p);
      |                        ~~~~~~^~~~~~~~~

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