Submission #953476

#	Time	Username	Problem	Language	Result	Execution time	Memory
953476		Pacybwoah	Sparklers (JOI17_sparklers)	C++17	0 / 100	0 ms	348 KiB

sparklers

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    ll t;
    cin>>n>>k>>t;
    vector<ll> vec(n+1);
    for(int i=1;i<=n;i++) cin>>vec[i];
    ll l=0,r=2e9/t;
    //l=8,r=9;
    while(l<r){
        ll mid=(l+r)>>1;
        ll vt=2*mid*t;
        int nowl=k-1,nowr=k+1;
        ll cnt=1;
        bool flag=0;
        if(k>1){
            if(vec[k]-vec[k-1]<=vt){
                cnt++;
                nowl=k-2;
                ll pos=vec[k]-vt;
                bool dir=0;
                while(nowl>0||nowr<=n){
                    if(!dir){
                        while(nowl>0&&pos-vec[nowl]<=vt){
                            pos-=vt;
                            nowl--;
                            cnt++;
                        }
                        pos=vec[nowl+1];
                        if(nowr>n){
                            if(nowl<1) flag=1;
                            break;
                        }
                        else if(vec[nowr]-pos<=vt*cnt){
                            cnt++;
                            pos=vec[nowr];
                            nowr++;
                            dir=!dir;
                        }
                        else{
                            break;
                        }
                    }
                    else{
                        while(nowr<=n&&vec[nowr]-pos<=vt){
                            pos+=vt;
                            nowr++;
                            cnt++;
                        }
                        pos=vec[nowr-1];
                        if(nowl<1){
                            if(nowr>n) flag=1;
                            break;
                        }
                        else if(pos-vec[nowl]<=vt*cnt){
                            cnt++;
                            pos=vec[nowl];
                            nowl--;
                            dir=!dir;
                        }
                        else{
                            break;
                        }
                    }
                }
                if(nowl<1&&nowr>n) flag=1;
            }
        }
        if(k<n){
            if(vec[k+1]-vec[k]<=vt){
                cnt=2;
                nowl=k-1,nowr=k+2;
                ll pos=vec[k]+vt;
                bool dir=1;
                while(nowl>0||nowr<=n){
                    //cout<<nowl<<" "<<nowr<<"\n";
                    if(!dir){
                        while(nowl>0&&pos-vec[nowl]<=vt){
                            pos-=vt;
                            nowl--;
                            cnt++;
                        }
                        pos=vec[nowl+1];
                        if(nowr>n){
                            if(nowl<1) flag=1;
                            break;
                        }
                        else if(vec[nowr]-pos<=vt*cnt){
                            cnt++;
                            pos=vec[nowr];
                            nowr++;
                            dir=!dir;
                        }
                        else{
                            break;
                        }
                    }
                    else{
                        while(nowr<=n&&vec[nowr]-pos<=vt){
                            pos+=vt;
                            nowr++;
                            cnt++;
                        }
                        pos=vec[nowr-1];
                        if(nowl<1){
                            if(nowr>n) flag=1;
                            break;
                        }
                        else if(pos-vec[nowl]<=vt*cnt){
                            cnt++;
                            pos=vec[nowl];
                            nowl--;
                            dir=!dir;
                        }
                        else{
                            break;
                        }
                    }
                }
                if(nowl<1&&nowr>n) flag=1;
            }
        }
        if(flag) r=mid;
        else l=mid+1;
    }
    cout<<l<<"\n";
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50