Submission #763389

#	Time	Username	Problem	Language	Result	Execution time	Memory
763389		burythelightdeepwithin	Xylophone (JOI18_xylophone)	C++14	0 / 100	3 ms	208 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

const int N = 5003;
int ans[N];
vector <int> w;

void solve(int n){
    w.push_back(n+1);
    int l = 1, r = n;
    while(l < r){
        int mid = (l+r)/2;
        int x = query(1, mid);
        if (x == (n-1)){
            r = mid;
        } else {
            l = mid+1;
        }
    }
    ans[l] = n;
    w.push_back(l);
    l = 1, r = n;
    while(l < r){
        int mid = (l+r)/2 + ((l+r) % 2);
        int x = query(mid, n);
        if (x == (n-1)){
            l = mid;
        } else {
            r = mid-1;
        }
    }
    ans[l] = 1;
    w.push_back(l);
    for (int k = n-1; k > 1; k--){
        sort(w.begin(), w.end());
        int reset = 0;
        int l = 1, r = w[0]-1;
        while(l < r){
            int mid = (l+r)/2 + ((l+r) % 2);
            int x = query(mid, w[0] - 1);
            if (x == abs(ans[w[0]] - k)){
                l = mid;
            } else {
                r = mid-1;
            }
        }
        if (l == r){
            int x = query(l, w[0]);
            if (x == abs(ans[w[0]] - k)){
                reset = 1;
            }
        }
        for (int i = 1; i < (int)w.size() - 1; i++){
            if (reset){
                 break;
            }
            l = w[i] + 1, r = w[i+1] - 1;
            while(l < r){
                int mid = (l+r)/2;
                int x = query(w[i], mid);
                if (x == abs(ans[w[i]] - k)){
                    r = mid;
                    reset = 1;
                } else {
                    l = mid+1;
                }
            }
            if (l == r){
                int x = query(w[i], l);
                if (x == abs(ans[w[i]] - k)){
                    reset = 1;
                }
            }
        }
        ans[l] = k;
        w.push_back(l);
    }
    for (int i = 1; i <= n; i++){
        answer(i, ans[i]);
    }
}

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