oj.uz

Submission #876602

# Submission time Handle Problem Language Result Execution time Memory
876602 2023-11-22T05:22:25 Z dsyz Xylophone (JOI18_xylophone) C++17
0 / 100
 0 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(i == posof1 + 2) cout<<"ADJDIFF: "<<adjdiff<<" "<<pos[i - 1]<<'\n';
		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);
			ll I1 = pos[i - 1] - adjdiff;
			ll I2 = pos[i - 1] + adjdiff;
			//if(i == posof1 + 2) cout<<"DIFF: "<<diff<<" "<<I1<<" "<<I2<<" "<<pos[i - 1]<<'\n';
			if(diff == abs(pos[i - 1] - pos[i - 2])){
				assert(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 - 1] - I1) || diff == abs(pos[i - 2] - I1)){
				pos[i] = I1;
				val[I1] = i;
			}else if(diff == abs(I2 - pos[i - 1]) || diff == abs(I2 - pos[i - 2])){
				pos[i] = I2;
				val[I2] = 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);
			ll I1 = pos[i + 1] - adjdiff;
			ll I2 = pos[i + 1] + adjdiff;
			if(diff == abs(pos[i + 1] - pos[i + 2])){
				assert(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 + 1] - I1) || diff == abs(pos[i + 2] - I1)){
				pos[i] = I1;
				//cout<<"I1: "<<I1<<'\n';
				val[I1] = i;
			}else if(diff == abs(I2 - pos[i + 1]) || diff == abs(I2 - pos[i + 2])){
				pos[i] = I2;
				//cout<<"I2: "<<I2<<'\n';
				val[I2] = i;
			}
		}
	}
	/*for(ll i = 1;i <= N;i++){
		cout<<"ANS: "<<pos[i]<<'\n';
	}*/
	for(ll i = 1;i <= N;i++){
		//cout<<"ANS: "<<pos[i]<<'\n';
		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 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 -