Submission #299818

#	Time	Username	Problem	Language	Result	Execution time	Memory
299818		limabeans	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	384 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 in
    {
	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;
    }

    auto bruteL = [&](int i) {
	//watch(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) break;	    
	}
    };

    auto bruteR = [&](int i) {
	// i, i+1, (i+2)
	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]) {
		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;
		}
		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) {
		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]);
	}
    }

    // cout<<"A: ";
    // for (int i=1; i<=n; i++) {
    // 	cout<<A[i]<<" ";
    // }
    // cout<<endl;
    // cout<<"go right"<<endl;

    // go right
    for (int i=in; i<n; i++) {
    	ask1(i);
    	int dif=A1[i];
    	if (isUsed(A[i]-dif)) {
    	    Set(i+1, A[i]+dif);
    	} else if (isUsed(A[i+1]+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;
	}
    }
}

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