제출 #654661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654661		uylulu	Xylophone (JOI18_xylophone)	C++14	47 / 100	95 ms	332 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] ;
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() ;
    assert(val>=1&&val<n) ;
    A[val] = 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>n)
            {
                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 ;
                    }
                }
            }
        }
    }
    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>n)
            {
                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 ;
                    }
                }
            }
        }
    }
    for(int i = 1; i<= n ; i++) answer(i , A[i]) ;
}

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