# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
36606 | 2017-12-11T20:21:09 Z | Flumen | Taxis (POI13_tak) | C++11 | 1000 ms | 9828 KB |
#include<bits/stdc++.h> using namespace std; long long a[500100],v[500100]; int main(){ int n,ans=600000,num,i,l,r,mid; long long m,d,tmp,tmp1,x; scanf("%lld%lld%d",&m,&d,&n); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); a[i]*=-1; } sort(a+1,a+n+1); for(i=1;i<=n;i++)a[i]*=-1; num=1; tmp=0; while(tmp<d){ num++; tmp1=tmp; tmp*=2; tmp+=(a[num]-d); if(tmp<=tmp1){ num--; break; } } //printf("%d\n",num); for(i=1;i<=num;i++){ v[i]=v[i-1]*2+(a[i]-d); //printf("%lld\n",v[i]); } for(i=n;i>=1;i--){ if(a[i]<m-d)continue; l=0;r=num; while(l<r){ mid=(l+r)/2; //printf("%d %d\n",i,mid); if(i>mid){ if(v[mid]>=d-((a[i]-m+d)/2))r=mid; else l=mid+1; } else{ if(mid-i>64)while(1); else x=v[i-1]*(1<<(mid-i))+v[mid]-v[i]*(1<<(mid-i)); if(x>=d-((a[i]-m+d)/2))r=mid; else l=mid+1; } } if(l<i){ if(v[l]>=d-((a[i]-m+d)/2))ans=min(ans,l+1); } else{ x=v[i-1]*(1<<(l-i))+v[l]-v[i]*(1<<(l-i)); if(x>=d-((a[i]-m+d)/2))ans=min(ans,l); } //printf("%d %d\n",i,l); } if(ans==600000)ans=0; printf("%d",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9828 KB | Output is correct |
2 | Correct | 0 ms | 9828 KB | Output is correct |
3 | Incorrect | 0 ms | 9828 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9828 KB | Output is correct |
2 | Correct | 0 ms | 9828 KB | Output is correct |
3 | Incorrect | 0 ms | 9828 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9828 KB | Output is correct |
2 | Execution timed out | 1000 ms | 9828 KB | Execution timed out |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9828 KB | Output is correct |
2 | Execution timed out | 1000 ms | 9828 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 9828 KB | Output is correct |
2 | Correct | 3 ms | 9828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 9828 KB | Output is correct |
2 | Execution timed out | 1000 ms | 9828 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 9828 KB | Output is correct |
2 | Execution timed out | 1000 ms | 9828 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 109 ms | 9828 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 156 ms | 9828 KB | Output is correct |
2 | Execution timed out | 1000 ms | 9828 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 9828 KB | Output is correct |
2 | Execution timed out | 1000 ms | 9828 KB | Execution timed out |