Submission #788009

#	Time	Username	Problem	Language	Result	Execution time	Memory
788009		Rafi22	Xylophone (JOI18_xylophone)	C++14	100 / 100	55 ms	452 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
 
using namespace std;
 
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
 
const int N=5007;
 
int a[N];
bool is[N];
 
void Set(int i,int x)
{
    a[i]=x;
    is[x]=1;
}
 
void solve(int n)
{
    int l=1,r=n,sr,k;
    while(l<=r)
    {
        sr=(l+r)/2;
        if(query(sr,n)==n-1)
        {
            k=sr;
            l=sr+1;
        }
        else r=sr-1;
    }
    Set(k,1);
    if(k+1<=n) Set(k+1,query(k,k+1)+1);
    for(int i=k+2;i<=n;i++)
    {
        int d=query(i-1,i);
        if(a[i-1]-d<1||is[a[i-1]-d]) Set(i,a[i-1]+d);
        else if(a[i-1]+d>n||is[a[i-1]+d]) Set(i,a[i-1]-d);
        else
        {
            int l=query(i-2,i);
            if(l==max(d,abs(a[i-1]-a[i-2])))
            {
                if(a[i-2]<a[i-1]) Set(i,a[i-1]-d);
                else Set(i,a[i-1]+d);
            }
            else
            {
                if(a[i-2]<a[i-1]) Set(i,a[i-1]+d);
                else Set(i,a[i-1]-d);
            }
        }
    }
    if(k-1>0) Set(k-1,query(k-1,k)+1);
    for(int i=k-2;i>0;i--)
    {
        int d=query(i,i+1);
        if(a[i+1]-d<1||is[a[i+1]-d]) Set(i,a[i+1]+d);
        else if(a[i+1]+d>n||is[a[i+1]+d]) Set(i,a[i+1]-d);
        else
        {
            int l=query(i,i+2);
            if(l==max(d,abs(a[i+1]-a[i+2])))
            {
                if(a[i+2]<a[i+1]) Set(i,a[i+1]-d);
                else Set(i,a[i+1]+d);
            }
            else
            {
                if(a[i+2]<a[i+1]) Set(i,a[i+1]+d);
                else Set(i,a[i+1]-d);
            }
        }
    }
    for(int i=1;i<=n;i++) answer(i,a[i]);
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve()
 
 
 
 
    return 0;
}*/

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:63:28: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     if(k-1>0) Set(k-1,query(k-1,k)+1);
      |                       ~~~~~^~~~~~~

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