Submission #210346

#	Time	Username	Problem	Language	Result	Execution time	Memory
210346		HNO2	Xylophone (JOI18_xylophone)	C++17	47 / 100	89 ms	532 KiB

xylophone

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

typedef long long ll;
const int maxn=1e6+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int ans[5007];
int used[5007];

void solve(int n)
{
    int L=1,R=n;
    while (R-L>1)
    {
        int M=(L+R)>>1;
        if (query(M,n)!=n-1) R=M;
        else L=M;
    }

    int _1_at=L;
    ans[_1_at]=1;
    if (_1_at!=n)
        ans[_1_at+1]=query(_1_at,_1_at+1)+1;
    if (_1_at!=1)
        ans[_1_at-1]=query(_1_at-1,_1_at)+1;
    for (int i=_1_at+1;i<=n-1;i++)
    {
        int tmp1=query(i,i+1),tmp2=query(i-1,i+1);
        if (tmp2==tmp1+abs(ans[i]-ans[i-1]))
        {
            if (ans[i]>ans[i-1]) ans[i+1]=ans[i-1]+tmp2;
            else ans[i+1]=ans[i-1]-tmp2;
        }
        else
        {
            if (ans[i]>ans[i-1]) ans[i+1]=ans[i]-tmp1;
            else ans[i+1]=ans[i]+tmp1;
        }
    }
    for (int i=_1_at;i<=n;i++) used[ans[i]]=1;
    for (int i=_1_at-1;i>=2;i--)
    {
        int tmp1=query(i-1,i);
        if (ans[i]-tmp1<1||used[ans[i]-tmp1])
        {
            ans[i-1]=ans[i]+tmp1;
            used[ans[i-1]]=1;
            continue;
        }
        if (ans[i]-tmp1>n||used[ans[i]+tmp1])
        {
            ans[i-1]=ans[i]-tmp1;
            used[ans[i-1]]=1;
            continue;
        }
        int tmp2=query(i-1,i+1);
        if (tmp2==tmp1+abs(ans[i]-ans[i+1]))
        {
            if (ans[i]>ans[i+1]) ans[i-1]=ans[i+1]+tmp2;
            else ans[i-1]=ans[i+1]-tmp2;
        }
        else
        {
            if (ans[i]>ans[i+1]) ans[i-1]=ans[i]-tmp1;
            else ans[i-1]=ans[i]+tmp1;
        }
        used[ans[i-1]]=1;
    }
    for (int i=1;i<=n;i++) answer(i,ans[i]);
}

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