oj.uz

Submission #981332

# Submission time Handle Problem Language Result Execution time Memory
981332 2024-05-13T04:33:35 Z Amaarsaa Xylophone (JOI18_xylophone) C++14
0 / 100
 0 ms 344 KB 
#include<bits/stdc++.h>
#include "xylophone.h"
 
using namespace std;
 
int a[5002], ans[5002];
/*
int query(int l, int r) {
	int mx, mn;
	mx = mn= a[l];
	for (int j = l; j <= r; j ++) mx = max(mx, a[j]), mn = min(mn, a[j]);
	return mx - mn;
}
*/
void solve(int N) {
	int mid,i, s,x1, x2, p, n = N, lo, hi;
	
	lo = 1;
	hi = n;
	while (lo < hi) {
		mid = (lo + hi)/2;
		if ( query(1, mid) == n - 1) hi = mid;
		else lo = mid + 1;
	}
	ans[lo] = n;
	ans[lo - 1] = n - query(lo - 1, lo); 
	for ( i = lo - 2; i >= 1; i --) {
		s = query(i, i + 1);
		p = query(i, i + 2);
		x1 = ans[i + 1] - s;
		x2 = ans[i + 1] + s;
		if ( max(x1, max(ans[i + 1], ans[i + 2])) - min(x1, min(ans[i + 1], ans[i + 2])) == p) {
			ans[i] = x1;
		} 
		if ( max(x2, max(ans[i + 1], ans[i + 2])) - min(x2, min(ans[i + 1], ans[i + 2])) == p) {
			ans[i] = x2;
		} 
		
	}
	ans[lo + 1] = n - query(lo, lo + 1); 
	for ( i = lo + 2; i <= n; i ++) {
		s = query(i - 1, i);
		p = query(i - 2, i);
		x1 = ans[i - 1] - s;
		x2 = ans[i - 1] + s;
		if ( x1 >= 1 && x1 <= n && max(x1, max(ans[i - 1], ans[i - 2])) - min(x1, min(ans[i - 1], ans[i - 2])) == p) {
			ans[i] = x1;
		} 
		if ( x2 >= 1 && x2 <= n && max(x2, max(ans[i - 1], ans[i - 2])) - min(x2, min(ans[i - 1], ans[i - 2])) == p) {
			ans[i] = x2;
		} 
		
	}
	for (i = 1; i <= n; i ++) answer(i, ans[i]);
 
}
/*
int main() {
	int n;
	
	cin >> n;
	
	for (int i = 1; i <= n; i ++) cin >> a[i];
	solve(n);
}
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -