/*
#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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
208 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
208 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
208 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
