Submission #655005

#	Time	Username	Problem	Language	Result	Execution time	Memory
655005		Hiennoob123	Xylophone (JOI18_xylophone)	C++14	100 / 100	65 ms	428 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
#define ll int
//#define int long long
#define ld long double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pld pair<ld,ld>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
ll n ;
ll A[100005] ;
bool check[100005] ;
ll find_one()
{
    ll lo = 1 , hi = n-1 , mid ;
    while(hi-lo>1)
    {
        mid = ((hi+lo)>>1) ;
        if(query(mid , n)==n-1)
        {
            lo = mid ;
        }
        else
        {
            hi = mid ;
        }
    }
    if(query(hi , n)==n-1) return hi ;
    else return lo ;
}
void solve(int m)
{
    n = m ;
    ll val = find_one() ;
    A[val] = 1 ;
    check[1] = 1 ;
    for(int i = val+1 ; i<= n ; i++)
    {
        if(i==val+1)
        {
            A[i] = A[i-1]+query(i-1 , i) ;
        }
        else
        {
            ll k = query(i-1 , i) ;
            if(k+A[i-1]>n)
            {
                A[i] = A[i-1]-k ;
            }
            else if(A[i-1]-k<=0)
            {
                A[i] = A[i-1]+k ;
            }
            else if(check[A[i-1]-k])
            {
                A[i] = A[i-1]+k ;
            }
            else if(check[A[i-1]+k])
            {
                A[i] = A[i-1]-k ;
            }
            else
            {
                ll q = query(i-2 , i) ;
                if(A[i-2]<A[i-1])
                {
                    if(A[i-1]-A[i-2]!=q)
                    {
                        if(k+A[i-1]-A[i-2]==q)
                        {
                            A[i] = A[i-1]+k ;
                        }
                        else
                        {
                            A[i] = A[i-1]-k ;
                        }
                    }
                    else
                    {
                        A[i] = A[i-1]-k ;
                    }
                }
                else
                {
                    if(A[i-2]-A[i-1]!=q)
                    {
                        if(k+A[i-2]-A[i-1]==q)
                        {
                            A[i] = A[i-1]-k ;
                        }
                        else
                        {
                            A[i] = A[i-1]+k ;
                        }
                    }
                    else
                    {
                        A[i] = A[i-1]+k ;
                    }
                }
            }
        }
        check[A[i]] = 1 ;
    }
    for(int i = val-1 ; i>= 1 ; i--)
    {
        if(i==val-1)
        {
            A[i] = A[i+1] + query(i , i+1) ;
        }
        else
        {
            ll k = query(i , i+1) ;
            if(k+A[i+1]>n)
            {
                A[i] = A[i+1]-k ;
            }
            else if(A[i+1]-k<=0)
            {
                A[i] = A[i+1]+k;
            }
            else if(check[A[i+1]-k])
            {
                A[i] = A[i+1]+k ;
            }
            else if(check[A[i+1]+k])
            {
                A[i] = A[i+1]-k ;
            }
            else
            {
                ll q = query(i , i+2) ;
                if(A[i+2]<A[i+1])
                {
                    if(A[i+1]-A[i+2]!=q)
                    {
                        if(k+A[i+1]-A[i+2]==q)
                        {
                            A[i] = A[i+1]+k ;
                        }
                        else
                        {
                            A[i] = A[i+1]-k ;
                        }
                    }
                    else
                    {
                        A[i] = A[i+1]-k ;
                    }
                }
                else
                {
                    if(A[i+2]-A[i+1]!=q)
                    {
                        if(k+A[i+2]-A[i+1]==q)
                        {
                            A[i] = A[i+1]-k ;
                        }
                        else
                        {
                            A[i] = A[i+1]+k ;
                        }
                    }
                    else
                    {
                        A[i] = A[i+1]+k ;
                    }
                }
            }
        }
        check[A[i]] = 1;
    }
    for(int i = 1; i<= n ; i++) answer(i , A[i]) ;
}

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