Submission #556836

#	Time	Username	Problem	Language	Result	Execution time	Memory
556836		fcmalkcin	Xylophone (JOI18_xylophone)	C++17	100 / 100	68 ms	560 KiB

xylophone

#include "xylophone.h"

#include <bits/stdc++.h>
using namespace std;

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+50;
const ll mod=1e9+7  ;
const ll base=1e9;
/// have a medal in APIO
/// goal 6/7

ll res[maxn];
bool dd[maxn];

bool chk(vector<ll> vt,ll mx,ll n)
{
    ll h=base;
    ll h1=-1;
    for (auto to:vt)
    {
        if (to>=1&&to<=n)
        {
            h1=max(h1,to);
            h=min(h,to);
        }
        else
        {
            return false;
        }
    }
    if (dd[vt[0]]) return false;
    if (h1-h!=mx)
        return false;
    return true;
}
void solve(ll n)
{
    ll l=1, h=n;
    while (l<=h)
    {
        ll mid=(l+h)/2;
        if (query(mid,n)!=n-1)
            h=mid-1;
        else
            l=mid+1;
    }
    ll p=h;
    res[p]=1;
    dd[1]=1;
    if (p>1)
    {
        res[p-1]=query(p-1,p)+1;
        dd[res[p-1]]=1;
    }
    for (int i=p-2; i>=1; i--)
    {
        ll h=query(i,i+1);
        vector<ll> vt;
        vt.pb(res[i+1]-h);
        vt.pb(res[i+1]+h);
        vector<ll> vt2;
        for (auto to:vt)
        {
            vector<ll> vt1;
            vt1.pb(to);
            vt1.pb(res[i+1]);
            if (chk(vt1,h,n))
            {
                vt2.pb(to);
            }
        }
        if (vt2.size()==2)
        {
            ll h=query(i,i+2);
            vt.clear();
            for (auto to:vt2)
            {
                vector<ll> vt1;
                vt1.pb(to);
                vt1.pb(res[i+1]);
                vt1.pb(res[i+2]);
                if (chk(vt1,h,n))
                {
                    vt.pb(to);
                }
            }
            assert(vt.size()==1);
            res[i]=vt.back();
        }
        else
        {
            res[i]=vt2.back();
        }
        dd[res[i]]=1;
    }
    if (p<n)
    {
        res[p+1]=query(p,p+1)+1;
        dd[res[p+1]]=1;
    }
    for (int i=p+2; i<=n; i++)
    {
        ll h=query(i-1,i);
        vector<ll> vt;
        vt.pb(res[i-1]-h);
        vt.pb(res[i-1]+h);
        vector<ll> vt2;
        for (auto to:vt)
        {
            vector<ll> vt1;
            vt1.pb(to);
            vt1.pb(res[i-1]);
            if (chk(vt1,h,n))
            {
                vt2.pb(to);
            }
        }
        if (vt2.size()==2)
        {
            ll h=query(i-2,i);
            vt.clear();
            for (auto to:vt2)
            {
                vector<ll> vt1;
                vt1.pb(to);
                vt1.pb(res[i-1]);
                vt1.pb(res[i-2]);
                if (chk(vt1,h,n))
                {
                    vt.pb(to);
                }
            }
            assert(vt.size()==1);
            res[i]=vt.back();
        }
        else
        {
            res[i]=vt2.back();
        }
        dd[res[i]]=1;
    }
    for (int i=1;i<=n;i++)
    {
        answer(i,res[i]);
    }
}

/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("CONVEXHULL.inp", "r"))
    {
        freopen("CONVEXHULL.inp", "r", stdin);
        freopen("CONVEXHULL.out", "w", stdout);
    }

}*/

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