Submission #67539

#	Time	Username	Problem	Language	Result	Execution time	Memory
67539		imeimi2000	Xylophone (JOI18_xylophone)	C++17	100 / 100	136 ms	1356 KiB

xylophone

#include "xylophone.h"
#include <algorithm>
#include <map>

using namespace std;
typedef pair<int, int> pii;

int n;
int dnc(int s, int e) {
    int m = (s + e) / 2;
    int ret;
    if ((ret = query(s, m)) == n - 1) return dnc(s, m);
    else if (query(m + 1, e) == n - 1) return dnc(m + 1, e);
    int i = s, j = m;
    while (i < j) {
        int d = (i + j + 1) / 2;
        if (query(d, e) == n - 1) i = d;
        else j = d - 1;
    }
    return i;
}

int q(int x, int y) {
    static map<pii, int> mp;
    if (mp.find(pii(x, y)) != mp.end()) return mp[pii(x, y)];
    return mp[pii(x, y)] = query(x, y);
}

static int a[5001];
void solve(int N) {
    n = N;
    a[1] = 0;
    a[2] = q(1, 2);
    for (int i = 2; i < n; ++i) {
        if (q(i - 1, i + 1) != q(i - 1, i) + q(i, i + 1)) {
            if (a[i - 1] < a[i]) a[i + 1] = a[i] - q(i, i + 1);
            else a[i + 1] = a[i] + q(i, i + 1);
        }
        else {
            if (a[i - 1] < a[i]) a[i + 1] = a[i] + q(i, i + 1);
            else a[i + 1] = a[i] - q(i, i + 1);
        }
    }
    int i = min_element(a + 1, a + (n + 1)) - a;
    int j = min_element(a + 1, a + (n + 1), greater<int>()) - a;
    if (i > j) {
        for (int i = 1; i <= n; ++i) a[i] = -a[i];
    }
    int x = (*min_element(a + 1, a + (n + 1))) - 1;
    for (int i = 1; i <= n; ++i) {
        answer(i, a[i] - x);
    }
}

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