oj.uz

Submission #680562

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 208 KB Wrong Answer [7]
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 1 ms 208 KB Output is correct
3 Incorrect 1 ms 208 KB Wrong Answer [7]
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 1 ms 208 KB Output is correct
3 Incorrect 1 ms 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -