Submission #299794

#	Time	Username	Problem	Language	Result	Execution time	Memory
299794		limabeans	Xylophone (JOI18_xylophone)	C++17	11 / 100	87 ms	504 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

void solve(int N);
int query(int s, int t);
void answer(int i, int a);


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

int A[maxn];

void Set(int i, int a) {
    answer(i,a);
    A[i]=a;
}

void solve(int l, int r, bool big, int idx) {
    if (r-l<=0) return;
    int gap = query(l,r);
    if (idx==l) {
	int lo = l;
	int hi = r;
	while (hi-lo>1) {
	    int m=(lo+hi)/2;
	    if (query(l,m)==gap) {
		hi = m;
	    } else {
		lo = m;
	    }
	}
	int mid = hi;
	// L....mid....r
	if (big) {
	    Set(mid,A[idx]-gap);
	    solve(l,mid-1,true,l);  // [l,mid)
	    solve(mid,r,false,mid); // [mid,r]
	} else {
	    Set(mid,A[idx]+gap);
	    solve(l,mid-1,false,l); // [l,mid)
	    solve(mid,r,true,mid);  // [mid,r]
	}
	
    } else if (idx==r) {
	int lo = l;
	int hi = r;
	while (hi-lo>1) {
	    int m=(lo+hi)/2;
	    if (query(m,r)==gap) {
		lo = m;
	    } else {
		hi = m;
	    }
	}
	int mid = lo;
	// l....mid....R
	if (big) {
	    Set(mid,A[idx]-gap);
	    solve(l,mid,false,mid);  // [l,mid]
	    solve(mid+1,r,true,r);   // (mid,r]
	} else {
	    Set(mid,A[idx]+gap);
	    solve(l,mid,true,mid);   // [l,mid]
	    solve(mid+1,r,false,r);  // (mid,r]
	}
    } else {
	assert(false);
    }
}




void solve(int n) {
    // find 1 and n
    int i1 = -1;
    int in = -1;
    for (int i=1; in==-1 && i<=n; i++) {
	for (int j=i; in==-1 && j<=n; j++) {
	    if (query(i,j)==n-1) {
		in=j;
		break;
	    }
	}
    }
    assert(~in);

    for (int j=in; i1==-1 && j>=1; j--) {
	if (query(j,in)==n-1) {
	    i1=j;
	    break;
	}
    }
    assert(~i1);

    Set(i1,1);
    Set(in,n);

    solve(1,i1,false,i1);
    solve(i1,in-1,false,i1);
    solve(in,n,true,in);
    // 1...i1.....in...n
}

///////////////////////////////////////////////////////////////////////////

/*
int nn;
vector<int> v = {-1,4,6,5,1,7,3,2,9,8};
int query(int s, int t) {
    assert(s<=t);
    int mx=0;
    for (int i=s; i<=t; i++) {
	for (int j=i; j<=t; j++) {
	    mx=max(mx,abs(v[i]-v[j]));
	}
    }
    return mx;
}


void answer(int i, int a) {
    A[i]=a;
}

void print() {
    cout<<"v: ";
    for (int i=1; i<=nn; i++) {
	cout<<v[i]<<" ";
    }
    cout<<endl;
    cout<<"A: ";
    for (int i=1; i<=nn; i++) {
	cout<<A[i]<<" ";
    }
    cout<<endl;
}

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;
}

vector<int> genV(int n) {
    vector<int> v = rand_perm(n, 1);
    v.insert(v.begin(), -1);
    int i1= -1; int in = -1;
    for (int i=1; i<=n; i++) {
	if (v[i]==1) i1=i;
	if (v[i]==n) in=i;
    }
    if (i1>in) {
	swap(v[i1],v[in]);
    }
    return v;
}

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

    v = genV(10);
    nn = (int)v.size() - 1;
    solve(nn);
    print();
    for (int i=1; i<=nn; i++) {
	assert(A[i]==v[i]);
    }
    
    
    return 0;
}

*/

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