Submission #419538

#	Time	Username	Problem	Language	Result	Execution time	Memory
419538		snasibov05	Xylophone (JOI18_xylophone)	C++14	100 / 100	82 ms	320 KiB

xylophone

#include "xylophone.h"
#include <vector>

using namespace std;

void solve(int n) {
    vector<int> ans(n+1);
    vector<bool> used(n+1);

    int l = 1, r = n;
	int first = 0;
	while (l <= r){
	    int mid = (l + r) / 2;
	    if (query(mid, n) == n-1){
	        first = mid;
	        l = mid + 1;
	    } else r = mid - 1;
	}

	ans[first] = 1;
	used[1] = true;

    for (int i = first - 1; i > 0; --i){
        int k = query(i, i+1);
        int x = ans[i+1] + k;
        int y = ans[i+1] - k;

        if (y < 1 || used[y]) ans[i] = x, used[x] = true;
        else if (x > n || used[x]) ans[i] = y, used[y] = true;
        else{

            int a = query(i, i+2);

            int mn = min(ans[i+1], ans[i+2]);
            int mx = max(ans[i+1], ans[i+2]);

            if (a == mx - mn && x > mn && x < mx) ans[i] = x, used[x] = true;
            else if (a == mx - mn) ans[i] = y, used[y] = true;
            else if (a == max(mx, x) - min(mn, x)) ans[i] = x, used[x] = true;
            else ans[i] = y, used[y] = true;

        }
    }

    for (int i = first + 1; i <= n; ++i){
        int k = query(i-1, i);
        int x = ans[i-1] + k;
        int y = ans[i-1] - k;

        if (y < 1 || used[y]) ans[i] = x, used[x] = true;
        else if (x > n || used[x]) ans[i] = y, used[y] = true;
        else{

            int a = query(i-2, i);

            int mn = min(ans[i-1], ans[i-2]);
            int mx = max(ans[i-1], ans[i-2]);

            if (a == mx - mn && x > mn && x < mx) ans[i] = x, used[x] = true;
            else if (a == mx - mn) ans[i] = y, used[y] = true;
            else if (a == max(mx, x) - min(mn, x)) ans[i] = x, used[x] = true;
            else ans[i] = y, used[y] = true;

        }
    }

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

}

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