Submission #285564

#TimeUsernameProblemLanguageResultExecution timeMemory
285564TadijaSebezSparklers (JOI17_sparklers)C++11
100 / 100
76 ms4508 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=100050; bool check(vector<ll> a,vector<ll> b){ if(a[0]<b[0])return 0; ll mx=a[0],mn=b[0]; int i=1,j=1; while(1){ if(i<a.size()&&a[i]>=mn)mx=max(mx,a[i++]); else if(j<b.size()&&b[j]<=mx)mn=min(mn,b[j++]); else break; } return i==a.size()&&j==b.size(); } ll x[N],t; int n,k; bool check(ll s){ vector<ll> a,b; for(int i=k;i>=1;i--)a.pb(x[i]-2*s*t*i); for(int i=k;i<=n;i++)b.pb(x[i]-2*s*t*i); if(!check(a,b))return 0; reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); return check(a,b); } int main(){ scanf("%i %i %lld",&n,&k,&t); for(int i=1;i<=n;i++)scanf("%lld",&x[i]); ll bot=0,top=1e9,mid,ans; while(top>=bot){ mid=top+bot>>1; if(check(mid))ans=mid,top=mid-1; else bot=mid+1; } printf("%lld\n",ans); return 0; }

Compilation message (stderr)

sparklers.cpp: In function 'bool check(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:11:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   if(i<a.size()&&a[i]>=mn)mx=max(mx,a[i++]);
      |      ~^~~~~~~~~
sparklers.cpp:12:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   else if(j<b.size()&&b[j]<=mx)mn=min(mn,b[j++]);
      |           ~^~~~~~~~~
sparklers.cpp:15:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  return i==a.size()&&j==b.size();
      |         ~^~~~~~~~~~
sparklers.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  return i==a.size()&&j==b.size();
      |                      ~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:33:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   mid=top+bot>>1;
      |       ~~~^~~~
sparklers.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%i %i %lld",&n,&k,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:30:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
      |                       ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...