Submission #702792

#	Time	Username	Problem	Language	Result	Execution time	Memory
702792		Halogen	Xylophone (JOI18_xylophone)	C++14	47 / 100	85 ms	296 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

int ans[5005];

void solve(int N) {

    int l, r;

    int bl = 1, br = N;

    while (bl <= br) {
        int m = bl + br >> 1;
        if (query(m, N) != N - 1) br = m - 1;
        else bl = m+1;
    }
    l = br;

    bl = 1, br = N;
    while (bl <= br) {
        int m = bl + br >> 1;
        if (query(1, m) != N - 1) bl = m + 1;
        else br = m-1;
    }
    r = bl;

    ans[l] = 1;
    ans[l + 1] = ans[l] + query(l, l + 1);
    if (l - 1 > 0) ans[l - 1] = ans[l] + query(l - 1, l);

    ans[r] = N;
    ans[r - 1] = ans[r] - query(r - 1, r);
    if (r + 1 <= N) ans[r + 1] = ans[r] - query(r, r + 1);

    for (int i = l - 1; i > 1; --i) {
        int diff = query(i - 1, i);

        if (diff + abs(ans[i] - ans[i + 1]) == query(i - 1, i + 1)) {
            if (ans[i] < ans[i + 1]) ans[i - 1] = ans[i] - diff;
            else ans[i - 1] = ans[i] + diff;
        }
        else {
            if (ans[i] < ans[i + 1]) ans[i - 1] = ans[i] + diff;
            else ans[i - 1] = ans[i] - diff;
        }
    }


    for (int i = r - 1; i > l + 2; --i) {
        int diff = query(i - 1, i);

        if (diff + abs(ans[i] - ans[i + 1]) == query(i - 1, i + 1)) {
            if (ans[i] < ans[i + 1]) ans[i - 1] = ans[i] - diff;
            else ans[i - 1] = ans[i] + diff;
        }
        else {
            if (ans[i] < ans[i + 1]) ans[i - 1] = ans[i] + diff;
            else ans[i - 1] = ans[i] - diff;
        }
    }


    for (int i = r + 1; i < N; ++i) {
        int diff = query(i, i + 1);

        if (diff + abs(ans[i] - ans[i - 1]) == query(i - 1, i + 1)) {
            if (ans[i - 1] > ans[i]) ans[i + 1] = ans[i] - diff;
            else ans[i + 1] = ans[i] + diff;
        }
        else {
            if (ans[i - 1] > ans[i]) ans[i + 1] = ans[i] + diff;
            else ans[i + 1] = ans[i] - diff;
        }
    }


    for (int i = 1; i <= N; i++) {
        answer(i, ans[i]);
    }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:14:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |         int m = bl + br >> 1;
      |                 ~~~^~~~
xylophone.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int m = bl + br >> 1;
      |                 ~~~^~~~

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