oj.uz

Submission #704231

# Submission time Handle Problem Language Result Execution time Memory
704231 2023-03-02T01:17:58 Z anhduc2701 Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 208 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x) (1LL<<(x))
#define task "tnc"  
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
int a[10005];
int ok[10005];
/*
int query(int l,int r){
	return 1;
}
int answer(int l,int r){
	return 1;
}
*/
void solve(int N){
	n=N;
	int l=1;
	int r=n-1;
	int vt1;
	while(l<=r){
		int mid=(l+r)/2;
		if(query(mid,n)==n-1){
			vt1=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	a[vt1]=1;
	ok[1]=1;
	if(vt1>1){
		int d=query(vt1-1,vt1);
		a[vt1-1]=1+d;
		ok[a[vt1-1]]=1;
		for(int i=vt1-2;i>=1;i--){
			int k=query(i,i+1);
			if(a[i+1]+k>=n ||(a[i+1]-k>=1 && ok[a[i+1]-k]==1)){
				a[i]=a[i+1]+k;
			}
			else if(a[i+1]-k<=1 || ok[a[i+1]+k]==1){
				a[i]=a[i+1]-k;
			}
			else{
				int k1=query(i,i+2);
				if(a[i+1]>a[i+2]){
					if(k==k1){
						a[i]=a[i+1]-k;
					}
					else if(a[i+1]-a[i+2]==k1){
						a[i]=a[i+1]-k;
					}
					else {//if(k<k1)
						a[i]=a[i+1]+k;
					}
				}
				else{
					if(k1>k){
						a[i]=a[i+1]-k;
					}
					else if(a[i+2]-a[i+1]==k1){
						a[i]=a[i+1]+k;
					}
					else{// k ==k1
						a[i]=a[i+1]+k;
					}
				}
			}
			ok[a[i]]=1;
		}
	}
	a[vt1+1]=1+query(vt1,vt1+1);
	ok[a[vt1+1]]=1;
	for(int i=vt1+2;i<=n;i++){
		int k=query(i-1,i);
		if(a[i-1]+k>n ||(a[i-1]-k>=1 && ok[a[i-1]-k]==1)){
			a[i]=a[i-1]+k;
		}
		else if(a[i-1]-k<=1 || ok[a[i-1]+k]==1){
			a[i]=a[i-1]-k;
		}
		else{
			int k1=query(i,i-2);
			if(a[i-1]>a[i-2]){
				if(k==k1){
					a[i]=a[i-1]-k;
				}
				else if(a[i-1]-a[i-2]==k1){
					a[i]=a[i-1]-k;
				}
				else {//if(k<k1)
					a[i]=a[i-1]+k;
				}
			}
			else{
				if(k1>k){
					a[i]=a[i-1]-k;
				}
				else if(a[i-2]-a[i-1]==k1){
					a[i]=a[i-1]+k;
				}
				else{// k ==k1
					a[i]=a[i-1]+k;
				}
			}
		}
		ok[a[i]]=1;
	}
	for(int i=1;i<=n;i++){
		answer(i,a[i]);
	}
}

Compilation message

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:46:6: warning: 'vt1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |  int vt1;
      |      ^~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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