제출 #338424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338424		KoD	Xylophone (JOI18_xylophone)	C++17	100 / 100	157 ms	98540 KiB

xylophone

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

#ifdef __APPLE__ 
int query(int, int);
void answer(int, int);
#else 
#include "xylophone.h"
#endif

void solve(int N) {
    Vec<Vec<int>> memo(N, Vec<int>(N, -1));
    const auto ask = [&](int s, int t) {
        if (memo[s][t] != -1) {
            return memo[s][t];
        }
        return memo[s][t] = query(s + 1, t + 1);
    };
    const auto fill = [&](Vec<int> &vec) {
        for (int i = 2; i < N; ++i) {
            const auto a = ask(i - 2, i - 1);
            const auto b = ask(i - 1, i);
            const auto c = ask(i - 2, i);
            if (vec[i - 2] < vec[i - 1]) {
                if (a + b == c) {
                    vec[i] = vec[i - 1] + b;
                }
                else {
                    vec[i] = vec[i - 1] - b;
                }
            }
            else {
                if (a + b == c) {
                    vec[i] = vec[i - 1] - b;
                }
                else {
                    vec[i] = vec[i - 1] + b;
                }
            }
        }
        const auto min = std::min_element(vec.begin(), vec.end());
        const auto max = std::max_element(vec.begin(), vec.end());
        const auto val = *min;
        for (auto &x: vec) {
            x -= val;
            x += 1;
        }
        return max - min > 0;
    };
    Vec<int> A(N);
    A[1] = ask(0, 1);
    if (fill(A)) {
        for (int i = 0; i < N; ++i) {
            answer(i + 1, A[i]);
        }
        return;
    }
    Vec<int> B(N);
    B[1] = -ask(0, 1);
    fill(B);
    for (int i = 0; i < N; ++i) {
        answer(i + 1, B[i]);
    }
}

#ifdef __APPLE__
int Size, QueryCount;
Vec<int> Array, Answer;
Vec<Vec<int>> Query;

int query(int s, int t) {
    QueryCount += 1;
    return Query[s - 1][t - 1];
}

void answer(int i, int a) {
    Answer[i - 1] = a;
}

int main() {
    std::cin >> Size;
    Array.resize(Size);
    Answer.resize(Size);
    Query.resize(Size);
    for (auto &x: Array) {
        std::cin >> x;
    }
    for (int i = 0; i < Size; ++i) {
        Query[i].resize(Size);
        int max = 0, min = Size + 1;
        for (int j = i; j < Size; ++j) {
            max = std::max(max, Array[j]);
            min = std::min(min, Array[j]);
            Query[i][j] = max - min;
        }
    }
    solve(Size);
    std::cout << "Number of queries: " << (double) QueryCount / (double) Size << "N\n";
    std::cout << (Array == Answer ? "Correct" : "Wrong") << '\n';
    for (auto x: Answer) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}
#endif

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