Submission #680559

#	Time	Username	Problem	Language	Result	Execution time	Memory
680559		nutella	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	336 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 mn = N, pos = hi;
    for (int i = hi - 1; i >= 0; --i) {
        int diff = query(i + 1, pos + 1);
        int a;

        if (diff + mn > N || was[diff + mn]) {
            a = mn - diff;
        } else if (mn - diff <= 0 || was[mn - diff]) {
            a = mn + diff;
        } else if (query(i + 1, hi + 1) == N - mn) {
            a = mn + diff;
        } else {
            a = mn - diff;
        }

        answer(i + 1, a);
        was[a] = true;
        if (mn > a) {
            mn = a;
            pos = i;
        }
    }

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

        if (diff + mn > N || was[diff + mn]) {
            a = mn - diff;
        } else if (mn - diff <= 0 || was[mn - diff]) {
            a = mn + diff;
        } else if (query(hi + 1, i + 1) == N - mn) {
            a = mn + diff;
        } else {
            a = mn - diff;
        }

        answer(i + 1, a);
        was[a] = true;
        if (mn > a) {
            mn = a;
            pos = i;
        }
    }
}

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;
      |                   ~~~^~~~

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