Submission #702820

#	Time	Username	Problem	Language	Result	Execution time	Memory
702820		Halogen	Xylophone (JOI18_xylophone)	C++14	47 / 100	83 ms	416 KiB

xylophone

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

int ans[5005];

void solve(int N) {
    int l;

    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;

    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);

    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 = l + 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:13:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         int m = bl + br >> 1;
      |                 ~~~^~~~

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