#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(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\n",bank,v);
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;
d2-=(long double)vreme*t;
poz=(poz+nxt.front())/2;
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;
d1-=(long double)vreme*t;
poz=(poz+prev.front())/2;
if(d1<0)
bank+=-1*d2/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
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))
~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
