oj.uz

Submission #680560

# Submission time Handle Problem Language Result Execution time Memory
680560 2023-01-11T08:02:26 Z nutella Xylophone (JOI18_xylophone) C++17
0 / 100
 2 ms 304 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 2 ms 304 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 2 ms 304 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 2 ms 304 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -