oj.uz

Submission #959574

# Submission time Handle Problem Language Result Execution time Memory
959574 2024-04-08T13:10:57 Z LCJLY Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 344 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<pii,pii>pi2;

static int A[5000];

void solve(int n) {
	//find index of value 1
	int l=1;
	int r=n;
	int mid;
	int one=1;
	
	while(l<=r){
		mid=(l+r)/2;
		int hold=query(mid,n);
		//show2(mid,mid,hold,hold);
		if(hold==n-1){
			one=mid;
			l=mid+1;;
		}
		else r=mid-1;
	}
	
	//show(one,one);
	
	int ans[n+5];
	memset(ans,-1,sizeof(ans));
	ans[one]=1;
	
	//neighbour values
	if(one>1){
		ans[one-1]=1+query(one-1,one);
	}
	if(one<n){
		ans[one+1]=1+query(one,one+1);
	}
	
	//recover other values
	for(int x=one-2;x>=1;x--){
		int a=query(x,x+1);
		int b=query(x,x+2);
		int diff=abs(ans[x+1]-ans[x+2]);
		if(b==diff&&a<b){
			//mid
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else if(a>b){
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else{
			if(ans[x+2]>ans[x+1]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
	}	
	
	for(int x=one+2;x<=n;x++){
		int a=query(x-1,x);
		int b=query(x-2,x);
		int diff=abs(ans[x-1]-ans[x-2]);
		if(b==diff&&a<b){
			//mid
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else if(a>b){
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else{
			if(ans[x-2]>ans[x-1]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
	}	
	

	//show4(ans,ans);
	
	for(int x=1;x<=n;x++){
		answer(x,ans[x]);
	}
}

//code

Compilation message

xylophone.cpp:12:12: warning: 'A' defined but not used [-Wunused-variable]
   12 | static int A[5000];
      |            ^

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 -