Submission #680562

#	Time	Username	Problem	Language	Result	Execution time	Memory
680562		nutella	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	208 KiB

xylophone

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

using namespace std;

void my_assert(bool f) {
    while (!f) {
        cout << "i am stupid" << endl;
    }
}

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;
                my_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 + 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;
                my_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:17:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         int mid = lo + hi >> 1;
      |                   ~~~^~~~
xylophone.cpp:44:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   44 |                 my_assert(p < a && a < pp || pp < a && a < p);
      |                           ~~~~~~^~~~~~~~~
xylophone.cpp:73:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |                 my_assert(p < a && a < pp || pp < a && a < p);
      |                           ~~~~~~^~~~~~~~~

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