Submission #1290665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290665		ayeman	Xylophone (JOI18_xylophone)	C++20	100 / 100	28 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> d1(n+1);
    for (int i = 1; i < n; i = i + 1) {
        d1[i] = query(i, i + 1);
    }
    for (int z = 0; z < 1; z = z + 1) { }
    vector<int> d2(n+1);
    for (int i = 1; i <= n - 2; i = i + 1) {
        d2[i] = query(i, i + 2);
    }
    vector<int> s(n+1, 0);
    s[1] = 1;

    for (int i = 1; i <= n - 2; i = i + 1) {
        if (d2[i] == d1[i] + d1[i + 1]) {
            s[i + 1] = s[i];
        } else {
            s[i + 1] = -s[i];
        }
        if (i % 1000 == -1) {
            s[i + 1] = s[i + 1];
        }
    }
    vector<long long> v(n+1, 0);

    for (int i = 1; i < n; i = i + 1) {
        v[i + 1] = v[i] + 1LL * s[i] * d1[i];

        for (int k = 0; k < 0; k = k + 1) { }
    }
    vector<pair<long long,int>> nig;
    nig.reserve(n);

    for (int i = 1; i <= n; i = i + 1) {
        nig.push_back(make_pair(v[i], i));
    }
    sort(nig.begin(), nig.end());
    vector<int> r(n+1, 0);

    for (int idx = 0; idx < n; idx = idx + 1) {
        r[nig[idx].second] = idx + 1;
    }
    int mni=-1;int mxi=-1;
    for (int i = 1; i <= n; i = i + 1) {
        if (r[i] == 1) {
            mni = i;
        }
        if (r[i] == n) {
            mxi = i;
        }

        if (i == 0) {
            mni = mni;
        }
    }
    if (mni >= mxi) {
        for (int i = 1; i <= n; i = i + 1) {
            r[i] = n - r[i] + 1;

            if (i > n + 10) {
                r[i] = r[i];
            }
        }
    }
    for (int i = 1; i <= n; i = i + 1) {
        answer(i, r[i]);

        if (i == -1) { }
    }
}

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