Submission #85379

#	Time	Username	Problem	Language	Result	Execution time	Memory
85379		nikolapesic2802	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	380 KiB

sparklers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
	os << '{';
	for(int i=0;i<sz(a);i++)
	{
		if(i>0&&i<sz(a)-1)
			os << ", ";
		os << a[i];
	}
	os << '}';
    return os;
}
bool test(long double poz,deque<int> prev,deque<int> nxt,int vreme,int t)
{
    //printf("Gledam %i\n",vreme);
    long double bank=0;
    long double v=(long double)vreme*t;
    while(prev.size()||nxt.size())
    {
        //printf("%lf %lf %lf\n",bank,v,poz);
        long double d1=LLONG_MAX;
        if(prev.size())
            d1=abs(prev.front()-poz);
        long double d2=LLONG_MAX;
        if(nxt.size())
            d2=abs(nxt.front()-poz);
        //printf("dist %lf %lf\n",d1,d2);
        if(!prev.size()||d2<d1)
        {
            //printf("Usao za nxt!\n");
            if(d2<=v)
            {
                bank+=vreme;
            }
            else
            {
                d2-=v;
                poz=(poz+(long double)vreme*t+nxt.front()-v)/2;
                d2-=(long double)vreme*t;
                if(d2<=0)
                    bank+=-1*d2/2;
                else
                {
                    bank-=d2;
                    poz+=d2;
                    if(bank<0)
                        return false;
                }
            }
            nxt.pop_front();
        }
        else
        {
            //printf("Usao za prev!\n");
            if(d1<=v)
            {
                bank+=vreme;
            }
            else
            {
                d1-=v;
                poz=(poz-(long double)vreme*t+prev.front()+v)/2;
                d1-=(long double)vreme*t;
                if(d1<=0)
                    bank+=-1*d1/2;
                else
                {
                    bank-=d1;
                    poz-=d1;
                    if(bank<0)
                        return false;
                }
            }
            prev.pop_front();
        }
        v+=(long double)vreme*t;
    }
    return true;
}
int main()
{
    int n,k,t;
    scanf("%i %i %i",&n,&k,&t);
    deque<int> prev,nxt;
    int poz;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%i",&a);
        if(i<k)
        {
            prev.push_front(a);
        }
        if(i>k)
        {
            nxt.pb(a);
        }
        if(i==k)
            poz=a;
    }
    int l=0,r=1e9;
    while(l<r)
    {
        int m=(l+r)>>1;
        if(test(poz,prev,nxt,m,t))
        {
            r=m;
        }
        else
        {
            l=m+1;
        }
    }
    printf("%i\n",l);
    return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i %i",&n,&k,&t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&a);
         ~~~~~^~~~~~~~~
sparklers.cpp:123:16: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(test(poz,prev,nxt,m,t))
            ~~~~^~~~~~~~~~~~~~~~~~

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