Submission #1290654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290654		hasandas	Xylophone (JOI18_xylophone)	C++20	100 / 100	39 ms	444 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;


void solve(const int N) {
    if (N == 1) {
        answer(1, 1);
        return;
    }

    vector<int> div1(N+1, 0);
    for (int i = 1; i <= N-1; ++i) {
        div1[i] = query(i, i+1);
    }

    vector<int> div2(N+1, 0);
    for (int i = 1; i <= N-2; ++i) {
        div2[i] = query(i, i+2);
    }

    vector<int> ss(N+1, 0);
    ss[1] = +1;

    for (int i = 1; i <= N-2; ++i) {
        if (div2[i] == div1[i] + div1[i+1]) {
            ss[i+1] = ss[i];
        } else {
            ss[i+1] = -ss[i];
        }
    }

    vector<long long> val(N+1, 0);
    val[1] = 0;
    for (int i = 1; i <= N-1; ++i) {
        val[i+1] = val[i] + 1LL * ss[i] * div1[i];
    }

    vector<pair<long long,int>> a;
    a.reserve(N);
    
    for (int i = 1; i <= N; ++i) {
        a.push_back({val[i], i});
    }

    sort(a.begin(), a.end());

    vector<int> rank(N+1, 0);

    for (int r = 0; r < N; ++r) {
        rank[a[r].second] = r + 1;
    }

    int pos_min = -1, pos_max = -1;
    for (int i = 1; i <= N; ++i) {
        if (rank[i] == 1) {
            pos_min = i;
        }
        if (rank[i] == N) {
            pos_max = i;
        }
    }
    if (pos_min >= pos_max) {
        for (int i = 1; i <= N; ++i) {
            rank[i] = N - rank[i] + 1;
        }
    }

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

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