Submission #233516

#	Time	Username	Problem	Language	Result	Execution time	Memory
233516		limabeans	Xylophone (JOI18_xylophone)	C++17	47 / 100	81 ms	500 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int n;
vector<int> a;

vector<int> p;


/*
//grader
int query(int s, int t) {
    int lo=1e9;
    int hi=-1e9;
    for (int i=s; i<=t; i++) {
	lo=min(lo,p[i]);
	hi=max(hi,p[i]);
    }
    return hi-lo;
}

void answer(int i, int a) {
    assert(i>=1 && i<=n);
    cout<<"a["<<i<<"]: "<<a<<endl;
    assert(p[i]==a);
}
//end grader
*/

int ask(int x, int y) {
    if (x>y) swap(x,y);
    return query(x,y);
}


void solveRange(int l, int r, int idx, bool idxMax=true) {
    if (l>=r) return;
    //cout<<"["<<l<<" "<<r<<"] : "<<idx<<" "<<hi<<endl;
    if (l+1==r) {
	int dx = query(l,r);
	if (idx==l) {
	    if (idxMax) a[r]=a[l]-dx; else a[r]=a[l]+dx;
	    answer(r,a[r]);
	} else {
	    if (idxMax) a[l]=a[r]-dx; else a[l]=a[r]+dx;
	    answer(l,a[l]);
	}
    } else {
	int d = query(l,r);
	if (idx==l) {
	    // for (int i=r; i>=l; i--) {
	    // 	int dx=query(l,i);
	    // 	if (dx<d) {
	    // 	    if (idxMax) a[i+1]=a[l]-d; else a[i+1]=a[l]+d;
	    // 	    answer(i+1,a[i+1]);
	    // 	    //l..i+1..r
	    // 	    solveRange(l,i,l,idxMax);
	    // 	    solveRange(i+1,r,i+1,!idxMax);
	    // 	    return;
	    // 	}
	    // }
	    int lo=l;
	    int hi=r+1;
	    while (hi-lo>1) {
	    	int mid=(hi+lo)/2;
	    	if (query(l,mid)<d) {
	    	    lo=mid;
	    	} else {
	    	    hi=mid;
	    	}
	    }
	    //l..i+1..r
	    int i = lo;
	    if (idxMax) a[i+1]=a[l]-d; else a[i+1]=a[l]+d;
	    answer(i+1,a[i+1]);

	    solveRange(l,i,l,idxMax);
	    solveRange(i+1,r,i+1,!idxMax);
	    return;
	    
	} else {
	    // for (int i=l; i<=r; i++) {
	    // 	int dx=query(i,r);
	    // 	if (dx<d) {
	    // 	    if (idxMax) a[i-1]=a[r]-d; else a[i-1]=a[r]+d;
	    // 	    answer(i-1,a[i-1]);
	    // 	    //l..i-1...r
	    // 	    solveRange(l,i-1,i-1,!idxMax);
	    // 	    solveRange(i,r,r,idxMax);
	    // 	    return;
	    // 	}
	    // }
	    int lo=l-1;
	    int hi=r;
	    while (hi-lo>1) {
	    	int mid=(lo+hi)/2;
	    	if (query(mid,r)<d) {
	    	    hi=mid;
	    	} else {
	    	    lo=mid;
	    	}
	    }
	    int i=hi;
	    if (idxMax) a[i-1]=a[r]-d; else a[i-1]=a[r]+d;
	    answer(i-1,a[i-1]);
	    //l..i-1...r
	    solveRange(l,i-1,i-1,!idxMax);
	    solveRange(i,r,r,idxMax);
	    return;
	}
	assert(0);
    }
}

void solve(int N) {
    n = N;
    a.resize(n+1, -1);
    int nIdx=-1;
    int lo=1;
    int hi=n+1;
    while (hi-lo>1) {
	int mid=(hi+lo)/2;
	if (query(1,mid)<n-1) {
	    lo=mid;
	} else {
	    hi=mid;
	}
    }
    nIdx=lo+1;
    a[nIdx]=n;
    answer(nIdx,a[nIdx]);
    assert(nIdx>=1&&nIdx<=n);
    solveRange(1,nIdx,nIdx);
    solveRange(nIdx,n,nIdx);
}

vector<int> rand_perm(int n, int index=1) {
    assert(n>=1);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> a(n);
    iota(a.begin(), a.end(), index);
    shuffle(a.begin(), a.end(), rng);
    return a;
}


/*
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    for (int i=0; i<10; i++) {
	int siz = 5;
	p=rand_perm(siz);
	//p={5,4,2,6,1,3};
	//p={1,3,6,5,4,2};
	p.insert(p.begin(), -1);
	int lo=1,hi=1;
	for (int i=1; i<=siz; i++) {
	    if (p[i]>p[hi]) hi=i;
	    if (p[i]<p[lo]) lo=i;
	}
	if (lo>hi) swap(p[lo],p[hi]);

	for (int i: p) cout<<i<<" ";
	cout<<endl;
    
	solve(siz);
    }

    return 0;
}
*/

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