Submission #419537

#	Time	Username	Problem	Language	Result	Execution time	Memory
419537		snasibov05	Xylophone (JOI18_xylophone)	C++14	0 / 100	1 ms	200 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 (x > mn && x < mx) ans[i] = y, used[y] = true;
            else ans[i] = x, used[x] = 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 (x > mn && x < mx) ans[i] = y, used[y] = true;
            else ans[i] = x, used[x] = true;

        }
    }

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

}

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