Submission #299845

#	Time	Username	Problem	Language	Result	Execution time	Memory
299845		limabeans	Xylophone (JOI18_xylophone)	C++17	100 / 100	72 ms	532 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];
int n;


bool used[maxn];
int A1[maxn];
int A2[maxn];

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


void ask1(int i) {
    if (A1[i]) return;
    A1[i] = query(i,i+1);
}

void ask2(int i) {
    assert(i+2<=n);
    if (A2[i]) return;
    A2[i] = query(i,i+2);
}

bool isUsed(int x) {
    if (x<1 || x>n) return true;
    return used[x];
}

void solve(int _n) {
    n=_n;
    int in = -1;
    // find where A[in]=n is
    {
	int lo = 1;
	int hi = n;
	while (hi-lo>1) {
	    int mid = (lo+hi)/2;
	    if (query(1,mid)==n-1) {
		hi = mid;
	    } else {
		lo = mid;
	    }
	}
	in = hi;
    }


    // A[i+1] and A[i+2] are fixed, solve for A[i]
    auto bruteL = [&](int i) {
	assert(i+2<=n);
	assert(A[i+1]); assert(A[i+2]);
	ask1(i);
	ask1(i+1);
	ask2(i);
	vector<int> op;
	op.push_back(A[i+1]-A1[i]);
	op.push_back(A[i+1]+A1[i]);
	for (int x: op) {
	    if (x<1 || x>n) continue;
	    A[i]=x;
	    bool ok = true;
	    int gap=max(abs(A[i]-A[i+1]),abs(A[i+1]-A[i+2]));
	    if (gap > A2[i]) {
		ok = false;
	    }
	    if (A1[i] < A2[i] && A1[i+1]==A2[i]) {
		// we have to be in the middle
		// 2 3 1 or 2 1 3
		int lo = min(A[i+1],A[i+2]);
		int hi = max(A[i+1],A[i+2]);
		if (!(lo<A[i] && A[i]<hi)) {
		    ok = false;
		}
	    } else if (A1[i]==A2[i] && A1[i+1]<A2[i]) {
		// 3 1 2 or 1 3 2
		if (A[i+1]<A[i+2]) {
		    if (!(A[i]>max(A[i+1],A[i+2]))) {
			ok = false;
		    }
		} else if (A[i+1]>A[i+2]) {
		    if (!(A[i]<min(A[i+1],A[i+2]))) {
			ok = false;
		    }
		} else {
		    assert(false);
		}
	    } else if (A1[i]<A2[i] && A1[i+1]<A2[i]) {
		// 1 2 3 or 3 2 1
		if (A[i+1]<A[i+2]) {
		    if (!(A[i]<A[i+1])) {
			ok = false;
		    }
		}
		if (A[i+1]>A[i+2]) {
		    if (!(A[i]>A[i+1])) {
			ok = false;
		    }
		}
	    } else {
		assert(false);
	    }

	    if (ok) {
		Set(i,x);
		break;
	    }
	}
    };

    // A[i] and A[i+1] are fixed, solve for A[i+2]
    auto bruteR = [&](int i) {
	ask1(i);
	ask2(i);
	ask1(i+1);
	assert(A[i]);
	assert(A[i+1]);
	vector<int> op;
	op.push_back(A[i+1]-A1[i+1]);
	op.push_back(A[i+1]+A1[i+1]);

	for (int x: op) {
	    if (x<1 || x>n) continue;
	    if (isUsed(x)) continue;
	    A[i+2] = x;
	    bool ok = true;
	    if (A1[i]<A2[i] && A1[i+1]<A2[i]) {
		// 1 2 3 or 3 2 1
		if (A[i]<A[i+1]) {
		    if (!(A[i+1]<A[i+2])) {
			ok = false;
		    }
		} else if (A[i]>A[i+1]) {
		    if (!(A[i+1]>A[i+2])) {
			ok = false;
		    }
		} else {
		    assert(false);
		}
	    } else if (A1[i]==A2[i] && A1[i+1]<A2[i]) {
		// 1 3 2 or 3 1 2
		int lo = min(A[i],A[i+1]);
		int hi = max(A[i],A[i+1]);
		if (!(lo<=A[i+2] && A[i+2]<=hi)) {
		    ok = false;
		}
	    } else if (A1[i+1]==A2[i] && A1[i]<A2[i]) {
		// 2 3 1
		// 2 1 3
		int lo = min(A[i+1],A[i+2]);
		int hi = max(A[i+1],A[i+2]);
		if (!(lo<=A[i] && A[i]<=hi)) {
		    ok = false;
		}
		if (A[i]>A[i+1]) {
		    if (!(A[i+2]>A[i])) {
			ok = false;
		    }
		} else if (A[i]<A[i+1]) {
		    if (!(A[i+2]<A[i])) {
			ok = false;
		    }
		} else {
		    assert(false);
		}
	    } else {
		assert(false);
	    }

	    if (ok) {
		Set(i+2,x);
		break;
	    }
	}

	// 1 2 3
	// 1 3 2
	// 2 1 3
	// 2 3 1
	// 3 1 2
	// 3 2 1
    };

    Set(in,n);
    // go left
    for (int i=in-1; i>=1; i--) {
	ask1(i);
	int dif=A1[i];
	if (isUsed(A[i+1]-dif)) {
	    Set(i, A[i+1]+dif);
	} else if (isUsed(A[i+1]+dif)) {
	    Set(i, A[i+1]-dif);
	} else {
	    assert(i+2<=n);
	    bruteL(i);
	    assert(A[i]);
	}
    }

    for (int i=in; i<n-1; i++) {
    	ask1(i);
    	int dif=A1[i];
    	if (isUsed(A[i]-dif)) {
    	    Set(i+1, A[i]+dif);
    	} else if (isUsed(A[i]+dif)) {
    	    Set(i+1, A[i]-dif);
    	} else {
    	    assert(i-1>=1);
    	    bruteR(i-1);
	    assert(A[i+1]);
    	}
    }

    for (int i=1; i<=n; i++) {
	if (!isUsed(i)) {
	    Set(n,i);
	    break;
	}
    }
}

///////////////////////////////////////////////////////////////////////////
/*

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

    //v = {-1, 1, 10, 2, 9, 3, 5, 8, 7, 6, 4};
    //v = {-1, 2, 1, 5, 7, 8, 3, 10, 9, 6, 4};
    //v = {-1, 6, 2, 5, 8, 7, 9, 1, 10, 3, 4 };
    // v = {-1,6, 1, 4, 10, 8, 9, 7, 3, 2, 5 };
    // v = {-1,2, 9, 1, 3, 10, 5, 6, 4, 7, 8};
    return v;
}

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

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

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