Submission #506171

#TimeUsernameProblemLanguageResultExecution timeMemory
506171Koosha_mvSparklers (JOI17_sparklers)C++14
100 / 100
111 ms6620 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first #define int ll const int N=2e5+9,inf=1e10+9; int n,k,t,a[N]; vector<int> g(vector<int> v,int x){ vector<int> res; int pos=0; f(i,0,v.size()){ if(v[i]>v[pos]){ pos=i; } } if(x==0){ f(i,0,pos+1){ res.pb(v[i]); } } else{ f_(i,v.size()-1,pos){ res.pb(v[i]); } } return res; } bool solve(vector<int> v0,vector<int> v1){ int p0=0,p1=0,mn0=inf,mn1=inf; if(v0[p0]+v1[p1]<0) return 0; // dbgv(v0); // dbgv(v1); f(i,1,v0.size()){ minm(mn0,v0[i]); if(v0[i]>=v0[0]){ break; } } f(i,1,v1.size()){ minm(mn1,v1[i]); if(v1[i]>=v1[0]){ break; } } // cout<<mn0<<" "<<mn1<<endl; while(p0+1<v0.size() || p1+1<v1.size()){ // cout<<p0<<" "<<p1<<endl; if(p0+1<v0.size() && mn0+v1[p1]>=0){ f(j,p0+1,v0.size()){ if(v0[j]>=v0[p0]){ p0=j; break; } } mn0=inf; f(j,p0+1,v0.size()){ minm(mn0,v0[j]); if(v0[j]>=v0[p0]){ break; } } } else if(p1+1<v1.size() && mn1+v0[p0]>=0){ f(j,p1+1,v1.size()){ if(v1[j]>=v1[p1]){ p1=j; break; } } mn1=inf; f(j,p1+1,v1.size()){ minm(mn1,v1[j]); if(v1[j]>=v1[p1]){ break; } } } else{ return 0; } } return 1; } bool check(int s){ vector<int> v0,v1; v0.pb(0); v1.pb(0); f_(i,k-1,0){ v0.pb(-(a[k]-a[i]-s*(k-i))); } f(i,k+1,n){ v1.pb(-(a[i]-a[k]-s*(i-k))); } // dbgv(v0); // dbgv(v1); return solve(g(v0,0),g(v1,0)) && solve(g(v0,1),g(v1,1)); } main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); cin>>n>>k>>t; k--; f(i,0,n){ cin>>a[i]; } //eror(check(150)); //exit(0); int l=-1,r=inf; while(l+1<r){ int mid=(l+r)>>1; if(check(2ll*t*mid)) r=mid; else l=mid; } cout<<r; }

Compilation message (stderr)

sparklers.cpp: In function 'std::vector<long long int> g(std::vector<long long int>, long long int)':
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   31 |  f(i,0,v.size()){
      |    ~~~~~~~~~~~~                
sparklers.cpp:31:2: note: in expansion of macro 'f'
   31 |  f(i,0,v.size()){
      |  ^
sparklers.cpp: In function 'bool solve(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   53 |  f(i,1,v0.size()){
      |    ~~~~~~~~~~~~~               
sparklers.cpp:53:2: note: in expansion of macro 'f'
   53 |  f(i,1,v0.size()){
      |  ^
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   59 |  f(i,1,v1.size()){
      |    ~~~~~~~~~~~~~               
sparklers.cpp:59:2: note: in expansion of macro 'f'
   59 |  f(i,1,v1.size()){
      |  ^
sparklers.cpp:66:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  while(p0+1<v0.size() || p1+1<v1.size()){
      |        ~~~~^~~~~~~~~~
sparklers.cpp:66:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  while(p0+1<v0.size() || p1+1<v1.size()){
      |                          ~~~~^~~~~~~~~~
sparklers.cpp:68:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(p0+1<v0.size() && mn0+v1[p1]>=0){
      |      ~~~~^~~~~~~~~~
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   69 |    f(j,p0+1,v0.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:69:4: note: in expansion of macro 'f'
   69 |    f(j,p0+1,v0.size()){
      |    ^
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   76 |    f(j,p0+1,v0.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:76:4: note: in expansion of macro 'f'
   76 |    f(j,p0+1,v0.size()){
      |    ^
sparklers.cpp:83:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   else if(p1+1<v1.size() && mn1+v0[p0]>=0){
      |           ~~~~^~~~~~~~~~
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   84 |    f(j,p1+1,v1.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:84:4: note: in expansion of macro 'f'
   84 |    f(j,p1+1,v1.size()){
      |    ^
sparklers.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   91 |    f(j,p1+1,v1.size()){
      |      ~~~~~~~~~~~~~~~~          
sparklers.cpp:91:4: note: in expansion of macro 'f'
   91 |    f(j,p1+1,v1.size()){
      |    ^
sparklers.cpp: At global scope:
sparklers.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...