oj.uz

Submission #1016159

# Submission time Handle Problem Language Result Execution time Memory
1016159 2024-07-07T12:54:51 Z vjudge1 Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 344 KB 
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;

void solve(int N) {
	int a[N+1];
	memset(a, 0, sizeof(a));
	// binary search pos of 1
	int lower = 1, upper = N;
	while(upper-lower>1){
		int mid = (upper+lower)/2;
		int x = query(mid, N);
		if(x==N-1) lower = mid;
		else upper = mid;
	}
	int pos1 = lower;
	a[pos1] = 1;
	if(pos1<N){
		// go to right
		int prev = query(pos1, pos1+1);
		a[pos1+1] = 1 + prev;
		for (int i=pos1+1; i<N; i++){
			int next = query(i, i+1);
			if(a[i]+next>N) a[i+1] = a[i]-next;
			else if(a[i]-next<1) a[i+1] = a[i]+next;
			else{
				int cur = query(i-1, i+1);
				if(cur==prev+next){
					if(a[i+1]>a[i]) a[i+1] = a[i]+next;
					else a[i+1] = a[i]-next;
				}
				else{
					if(a[i+1]>a[i]) a[i+1] = a[i]-next;
					else a[i+1] = a[i]+next;
				}
			}
			prev = next;
		}
	}
	if(pos1>1){
		// go to left
		int prev = query(pos1-1, pos1);
		a[pos1-1] = 1 + prev;
		for (int i=pos1-1; i>1; i--){
			int next = query(i-1, i);
			if(a[i]+next>N) a[i-1] = a[i]-next;
			else if(a[i]-next<1) a[i-1] = a[i]+next;
			else{
				int cur = query(i-1, i+1);
				if(cur==prev+next){
					if(a[i-1]>a[i]) a[i-1] = a[i]+next;
					else a[i-1] = a[i]-next;
				}
				else{
					if(a[i-1]>a[i]) a[i-1] = a[i]-next;
					else a[i-1] = a[i]+next;
				}
			}
			prev = next;
		}
	}
	for (int i=1; i<=N; i++) answer(i, a[i]);
	return;
}

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 0 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 0 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 0 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -