Submission #762964

#	Time	Username	Problem	Language	Result	Execution time	Memory
762964		adaawf	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	592 KiB

xylophone

#include "xylophone.h"
#include <iostream>
#include <vector>
using namespace std;
int a[5005];
vector<int> g[5005];
void solve(int N) {
    int ma = 0, l = 0;
    for (int i = 2; i <= N; i++) {
        int h = query(1, i);
        ma = max(ma, h);
        g[h].push_back(i);
    }
    if (g[ma].size() == 2) {
        int h = g[ma][0], k = g[ma][1];
        if (h < k) a[h] = 1, a[k] = N, l = h;
        else a[h] = N, a[k] = 1, l = k;
    }
    else {
        int h = g[ma][0];
        int d = N - ma, e = ma + 1;
        int t = g[d - 1][0], tt = g[d - 1][1];
        int k = query(t, h), kk = query(tt, h);
        if (k == N - 1) {
            if (t > h) swap(t, h);
            a[t] = 1;
            a[h] = N;
            a[1] = d;
            l = t;
        }
        else if (kk == N - 1) {
            if (tt > h) swap(tt, h);
            a[tt] = 1;
            a[h] = N;
            a[1] = d;
            l = tt;
        }
        else {
            t = g[N - e][0], tt = g[N - e][1];
            k = query(t, h), kk = query(tt, h);
            if (k == N - 1) {
                if (t < h) swap(t, h);
                a[h] = 1;
                a[t] = N;
                a[1] = e;
                l = h;
            }
            else if (kk == N - 1) {
                if (tt < h) swap(tt, h);
                a[h] = 1;
                a[tt] = N;
                a[1] = e;
                l = h;
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if (a[i] == 0) {
            int h = query(i, l);
            a[i] = h + 1;
        }
    }
    for (int i = 1; i <= N; i++) answer(i, a[i]);
}

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