Submission #394995

#	Time	Username	Problem	Language	Result	Execution time	Memory
394995		Victor	Xylophone (JOI18_xylophone)	C++17	100 / 100	170 ms	452 KiB

xylophone

#include "xylophone.h"

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

void solve(int n) {
    int diff[5001], ans[5001], dir[5001];
    
    rep(i, 0, n - 1) diff[i] = query(i + 1, i + 2);
    rep(i, 1, n - 1) {
        int val = query(i, i + 2);
        dir[i] = val != diff[i - 1] + diff[i];
    }

    rep(i, 0, n) {
        bitset<5001> vis;
        ans[0] = i + 1;
        ans[1] = ans[0] + diff[0];
        if (ans[1] < 1 || n < ans[1]) continue;
        vis[i + 1] = vis[ans[1]] = 1;

        int cd = 1;
        bool works = 1, lo = i==0, rev = 0;

        rep(i, 1, n - 1) {
            if (ans[i] == n && !lo) rev = 1;
            if (ans[i] == 1) lo = 1;

            cd ^= dir[i];
            ans[i + 1] = ans[i] + (cd ? diff[i] : -diff[i]);

            if (ans[i + 1] < 1 || n < ans[i + 1] || vis[ans[i + 1]]) {
                works = 0;
                break;
            }
            vis[ans[i + 1]] = 1;
        }
        if (ans[n - 1] < 1 || n < ans[n - 1]) works = 0;

        if (works) {
            if (rev) rep(i, 0, n) ans[i] = n - ans[i] + 1;
            break;
        }
    }

    rep(i, 0, n) answer(i + 1, ans[i]);
}

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