Submission #1318636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318636		em4ma2	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	332 KiB

xylophone

#include "bits/stdc++.h"
#include "xylophone.h"

using namespace std;

//#define int long long
#define ll long long
#define pb push_back

const int inf=LLONG_MAX;



void solve(int n){
    int l=1,r=n;
    vector<int>a(n+1,-1);
    int x=0;
    while (l<=r){
        int mid=(l+r)/2;
        if (query(1,mid)==n-1){
            x=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    vector<int>vis(n+1);
    a[x]=n;
    vis[a[x]]=1;
    l=x;
    for (int i=l-1;i>0;i--){
        x=query(i,i+1);
        if (a[i+1]+x>n || vis[a[i+1]+x]){
            a[i]=a[i+1]-x;
            vis[a[i]]=1;
        }else if (a[i+1]-x<1 || vis[a[i+1]-x]){
            a[i]=a[i+1]+x;
            vis[a[i]]=1;
        }else{
            int a1=a[i+1]+x,a2=a[i+1]-x;
            int eh=query(i,i+2);
            if ((max({a[i+1],a[i+2],a1})-min({a[i+1],a[i+2],a1}))==eh){
                a[i]=a1;
                vis[a[i]]=1;
            }else{
                a[i]=a2;
                vis[a[i]]=1;
            }
        }
    }
    for (int i=l+1;i<=n;i++){
        x=query(i,i-1);
        if (a[i-1]+x>n || vis[a[i-1]+x]){
            a[i]=a[i-1]-x;
            vis[a[i]]=1;
        }else if (a[i-1]-x<1 || vis[a[i-1]-x]){
            a[i]=a[i-1]+x;
            vis[a[i]]=1;
        }else{
            int a1=a[i-1]+x,a2=a[i-1]-x;
            int eh=query(i,i-2);
            if ((max({a[i-1],a[i-2],a1})-min({a[i-1],a[i-2],a1}))==eh){
                a[i]=a1;
                vis[a[i]]=1;
            }else{
                a[i]=a2;
                vis[a[i]]=1;
            }
        }
    }
    for (int i=1;i<=n;i++){
        answer(i,a[i]);
    }
}

// signed main(){
//     ios::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

   

//     return 0;
// }

Compilation message (stderr)

xylophone.cpp:10:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   10 | const int inf=LLONG_MAX;
      |               ^~~~~~~~~

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