oj.uz

Submission #1070423

# Submission time Handle Problem Language Result Execution time Memory
1070423 2024-08-22T14:07:09 Z _8_8_ Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 344 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int p[5002],a[5002];
void solve(int n) {
	int nd = n - 1;
	int l = 1,r = n;
	while(r - l > 1) {
		int mid = (l + r) >> 1;
		if(query(1,mid) == nd) {
			r = mid;
		} else {
			l = mid;
		}
	}
	p[n] = r;
	l = 1,r = p[n];
	while(r - l > 1) {
		int mid = (l + r) >> 1;
		if(query(mid,r) == nd) {
			l = mid;
		} else {
			r = mid;
		}
	}
	p[1] = l;
	a[p[1]] = 1;
	a[p[n]] = n;
	int mx = 1;
	for(int i = p[1] - 1;i >= 1;i--) {
		int val, T;
		T = query(i,p[1]);
		if(T != mx - 1) {
			val = mx = 1 + T;
		} else {
			int t2, t1;
			t2 = query(i,i + 2);
			t1 = query(i + 1,i + 2);
			int t = query(i,i + 1);
			//a[i] = a[i + 1] - t or a[i] = a[i + 1] + t
			if(a[i + 2] > a[i + 1]) {
				if(t2 != t1) {
					val = a[i + 1] - t;
				} else {
					val = a[i + 1] + t;
				}
			} else {
				if(t2 != t1) {
					val = a[i + 1] + t;
				} else {
					val = a[i + 1] - t;
				}
			}
		}
		p[val] = i;
		a[i] = val;
	}
	mx = 1;
	for(int i = p[1] + 1;i < p[n];i++) {
		int val, T;
		T = query(p[1],i);	
		if(T != mx - 1) {
			val = mx = 1 + T;
		} else {
			int t2, t1;
			t2 = query(i - 2,i - 1);
			t1 = query(i - 2,i);
			int t = query(i - 1,i);
			if(a[i - 2] > a[i - 1]) {
				if(t2 != t1) {
					val = a[i - 1] - t;
				} else {
					val = a[i - 1] + t;
				}
			} else {
				if(t2 != t1) {
					val = a[i - 1] + t;
				} else {
					val = a[i - 1] - t;
				}
			}
		}
		p[val] = i;
		a[i] = val;
	}
	int mn = n;
	for(int i = p[n] + 1;i <= n;i++) {
		int val, T = query(p[n],i);
		if(T != n - mn) {
			mn = val = n - T;
		} else {
			int t1, t2;
			t2 = query(i - 2,i - 1);
			t1 = query(i - 2,i);
			int t = query(i - 1,i);
			if(a[i - 2] > a[i - 1]) {
				if(t2 != t1) {
					val = a[i - 1] - t;
				} else {
					val = a[i - 1] + t;
				}
			} else {
				if(t2 != t1) {
					val = a[i - 1] + t;
				} else {
					val = a[i - 1] - t;
				}
			}	
		}
		p[val] = i;
		a[i] = val;
	}
	for(int i = 1;i <= n;i++) {
		answer(p[i],i);
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -