Submission #654637

#	Time	Username	Problem	Language	Result	Execution time	Memory
654637		anhduc2701	Xylophone (JOI18_xylophone)	C++17	100 / 100	68 ms	448 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
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>;
#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))
int n;
int a[5005];
int ok[10005];
void solve(int n){
	int l=1;
	int r=n;
	int pos;
	while(l<=r){
		int mid=(l+r)/2;
		if(query(mid,n)>=n-1){
			pos=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	a[pos]=1;
	if(pos>1){
		a[pos-1]=1+query(pos-1,pos);
		ok[a[pos-1]]=1;
		ok[1]=1;
		for(int i=pos-2;i>=1;i--){
			int hieu=query(i,i+1);
			if(a[i+1]+hieu>n || ok[a[i+1]+hieu]==1){
				a[i]=a[i+1]-hieu;
				ok[a[i]]=1;
				continue;
			}
			if(a[i+1]-hieu<1 || ok[a[i+1]-hieu]==1){
				a[i]=a[i+1]+hieu;
				ok[a[i]]=1;
				continue;
			}
			int hieumoi=query(i,i+2);
			if(a[i+1]>a[i+2]){
                if(hieumoi==a[i+1]-a[i+2]){
                    a[i]=a[i+1]-hieu;
                }
                if(hieumoi==hieu+a[i+1]-a[i+2]){
                    a[i]=a[i+1]+hieu;
                }
                else if(hieumoi==hieu){
                    a[i]=a[i+1]-hieu;
                }
			}
			else{
                if(hieumoi==a[i+2]-a[i+1]){
                    a[i]=a[i+1]+hieu;
                }
                if(hieumoi==hieu){
                    a[i]=a[i+1]+hieu;
                }
                if(hieumoi==hieu+a[i+2]-a[i+1]){
                    a[i]=a[i+1]-hieu;
                }
			}
			ok[a[i]]=1;
		}
	}
	if(pos<n){
        a[pos+1]=1+query(pos,pos+1);
		ok[a[pos+1]]=1;
		for(int i=pos+2;i<=n;i++){
			int hieu=query(i-1,i);
			if(a[i-1]+hieu>n || ok[a[i-1]+hieu]==1){
				a[i]=a[i-1]-hieu;
				ok[a[i]]=1;
				continue;
			}
			if(a[i-1]-hieu<1 || ok[a[i-1]-hieu]==1){
				a[i]=a[i-1]+hieu;
				ok[a[i]]=1;
				continue;
			}
			int hieumoi=query(i-2,i);
			if(a[i-1]>a[i-2]){
                if(hieumoi==a[i-1]-a[i-2]){
                    a[i]=a[i-1]-hieu;
                }
                if(hieumoi==hieu+a[i-1]-a[i-2]){
                    a[i]=a[i-1]+hieu;
                }
                if(hieumoi==hieu){
                    a[i]=a[i-1]-hieu;
                }
			}
			else{
                if(hieumoi==a[i-2]-a[i-1]){
                    a[i]=a[i-1]+hieu;
                }
                if(hieumoi==hieu){
                    a[i]=a[i-1]+hieu;
                }
                if(hieumoi==hieu+a[i-2]-a[i-1]){
                    a[i]=a[i-1]-hieu;
                }
			}
			ok[a[i]]=1;
		}
	}
	for(int i=1;i<=n;i++){
        answer(i,a[i]);
	}
	return;
}

Compilation message (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53