Submission #381103

#	Time	Username	Problem	Language	Result	Execution time	Memory
381103		knightron0	Xylophone (JOI18_xylophone)	C++14	100 / 100	124 ms	768 KiB

xylophone

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

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

// int a[MAXN];

// int query(int s, int t){
// 	int mx = -MAXN, mn = MAXN;
// 	for(int i= s;i<=t;i++){
// 		mx = max(mx,a[i]);
// 		mn = min(mn,a[i]);
// 	}
// 	return mx-mn;
// }

void solve(int N){
	int nxt[N+2];
	for(int i=1;i<N;i++){
		nxt[i] = query(i, i+1);
	}
	int x[N+2];
	x[1] = 1;
	for(int i=1;i<N-1;i++){
		int vl = query(i, i+2);
		if(vl == nxt[i] || vl == nxt[i+1]){
			x[i+1] = x[i] ^ 1;
		} else {
			x[i+1] = x[i];
		}
	}
	int b[N+2], c[N+2];
	b[1] = 0, c[1] = 0;
	for(int i= 1;i<N;i++){
		if(x[i] == 1){
			b[i+1] = b[i] + nxt[i];
			c[i+1] = c[i] - nxt[i];
		} else {
			b[i+1] = b[i] - nxt[i];
			c[i+1] = c[i] + nxt[i];
		}
	}
	int mxb = -MAXN; int mxc = -MAXN;
	for(int i = 1;i<=N;i++){
		mxb = max(mxb, b[i]);
		mxc = max(mxc, c[i]);
	}
	int diffb = N-mxb;
	int diffc = N-mxc;
	int idx[2] = {0, 0};
	for(int i= 1;i<=N;i++){
		b[i] += diffb;
		c[i] += diffc;
		if(b[i] == 1) idx[0] = i;
		if(b[i] == N) idx[1] = i;
	}
	int ans[N+2];
	for(int i= 1;i<=N;i++) {
		if(idx[0] < idx[1]){
			ans[i] = b[i];
		} else {
			ans[i] = c[i];
		}
		answer(i, ans[i]);
	}
}


// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     #ifdef LOCAL
//     freopen("input.txt", "r", stdin);
//     #endif
//    	int n;
//    	cin>>n;
//    	for(int i= 1;i<=n;i++){
//    		cin>>a[i];
//    	}
//    	solve(n);
//     return 0;
// }

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