oj.uz

Submission #876316

# Submission time Handle Problem Language Result Execution time Memory
876316 2023-11-21T14:32:13 Z dsyz Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)

void solve(int N) {
	ll low = 1;
	ll high = N + 1;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		ll diff = query(mid,N);
		if(diff == N - 1){
			low = mid;
		}else{
			high = mid;
		}
	}
	ll posof1 = low;
	ll val[N + 1]; //pos of value i
	memset(val,-1,sizeof(val));
	val[1] = posof1;
	ll pos[N + 1]; //value of pos i
	memset(pos,-1,sizeof(pos));
	pos[posof1] = 1;
	for(ll i = posof1 + 1;i <= N;i++){ //all index are 1-indexed
		ll adjdiff = query(i - 1,i);
		if(pos[i - 1] - adjdiff < 1 || val[pos[i - 1] - adjdiff] != -1){
			pos[i] = pos[i - 1] + adjdiff;
			val[pos[i - 1] + adjdiff] = i;
		}else if(pos[i - 1] + adjdiff > N || val[pos[i - 1] + adjdiff] != -1){
			pos[i] = pos[i - 1] - adjdiff;
			val[pos[i - 1] - adjdiff] = i;
		}else{ //i can prove this is at least 2 spaces away from val 1
			ll diff = query(i - 2,i);
			if(diff == abs(pos[i - 1] - pos[i - 2])){
				if(pos[i - 1] > pos[i - 2]){
					pos[i] = pos[i - 1] - adjdiff;
					val[pos[i - 1] - adjdiff] = i;
				}else{
					pos[i] = pos[i - 1] + adjdiff;
					val[pos[i - 1] + adjdiff] = i;
				}
			}else if(diff == abs(pos[i] - pos[i - 1])){
				if(pos[i - 1] > pos[i - 2]){
					pos[i] = pos[i - 1] - adjdiff;
					val[pos[i - 1] - adjdiff] = i;
				}else{
					pos[i] = pos[i - 1] + adjdiff;
					val[pos[i - 1] + adjdiff] = i;
				}
			}else if(diff == abs(pos[i] - pos[i - 2])){
				if(pos[i - 1] > pos[i - 2]){
					pos[i] = pos[i - 1] + adjdiff;
					val[pos[i - 1] + adjdiff] = i;
				}else{
					pos[i] = pos[i - 1] - adjdiff;
					val[pos[i - 1] - adjdiff] = i;
				}
			}
		}
	}
	
	for(ll i = posof1 - 1;i >= 1;i--){ //all index are 1-indexed
		ll adjdiff = query(i,i + 1);
		if(pos[i + 1] - adjdiff < 1 || val[pos[i + 1] - adjdiff] != -1){
			pos[i] = pos[i + 1] + adjdiff;
			val[pos[i + 1] + adjdiff] = i;
		}else if(pos[i + 1] + adjdiff > N || val[pos[i + 1] + adjdiff] != -1){
			pos[i] = pos[i + 1] - adjdiff;
			val[pos[i + 1] - adjdiff] = i;
		}else{ //i can prove this is at least 2 spaces away from val 1
			ll diff = query(i,i + 2);
			if(diff == abs(pos[i + 1] - pos[i + 2])){
				if(pos[i + 1] > pos[i + 2]){
					pos[i] = pos[i + 1] - adjdiff;
					val[pos[i + 1] - adjdiff] = i;
				}else{
					pos[i] = pos[i + 1] + adjdiff;
					val[pos[i + 1] + adjdiff] = i;
				}
			}else if(diff == abs(pos[i] - pos[i + 1])){
				if(pos[i + 1] > pos[i + 2]){
					pos[i] = pos[i + 1] - adjdiff;
					val[pos[i + 1] - adjdiff] = i;
				}else{
					pos[i] = pos[i + 1] + adjdiff;
					val[pos[i + 1] + adjdiff] = i;
				}
			}else if(diff == abs(pos[i] - pos[i + 2])){
				if(pos[i + 1] > pos[i + 2]){
					pos[i] = pos[i + 1] + adjdiff;
					val[pos[i + 1] + adjdiff] = i;
				}else{
					pos[i] = pos[i + 1] - adjdiff;
					val[pos[i + 1] - adjdiff] = i;
				}
			}
		}
	}
	for(ll i = 1;i <= N;i++){
		answer(i,pos[i]);
	}
}

Subtask #1
0 / 11.0

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