Submission #347815

#	Time	Username	Problem	Language	Result	Execution time	Memory
347815		quekyp	Xylophone (JOI18_xylophone)	C++14	100 / 100	131 ms	620 KiB

xylophone

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

using namespace std;

static int A[5050];

void solve(int N) {

    // gaps of 1 and 2
    int d1[5050];
    int d2[5050];

    // O(2N) queries
    for (int i = 1; i < N; i++) {
        d1[i] = query(i, i + 1);
        if (i < N - 1)
            d2[i] = query(i, i + 2);
    }

    // change direction?
    bool change[5050];

    for (int i = 1; i < N - 1; i++) {
        change[i] = !(d1[i] + d1[i + 1] == d2[i]);
    }

    int number = 0;
    int direction = 1;
    A[0] = number;
    for (int i = 1; i < N; i++) {
        number += d1[i] * direction;
        A[i] = number;
        if (i < N - 1 && change[i]) direction *= -1;
    }

    // min, max
    int min_ = 5001, min_index = 0;
    int max_ = -1, max_index = 0;
    for (int i = 0; i < N; i++) {
        int a = A[i];
        if (a < min_) {
            min_ = a;
            min_index = i;
        }
        if (a > max_) {
            max_ = a;
            max_index = i;
        }
    }

    // offset
    min_--;
    for (int i = 0; i < N; i++) {
        A[i] -= min_;
    }

    // reverse
    if (min_index > max_index) {
        for (int i = 0; i < N; i++) {
            A[i] = N - A[i] + 1;
        }
    }

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

}

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