Submission #558282

#TimeUsernameProblemLanguageResultExecution timeMemory
558282Koosha_mvA Difficult(y) Choice (BOI21_books)C++14
100 / 100
1 ms220 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 #include "books.h" const int N=1e5+99; ll n,t,a[N]; /* void impossible(){ cout<<"Impossible"; exit(0); } void answer(vector<ll> ans){ dbgv(ans); exit(0); } ll skim(ll x){ return a[x]; }*/ void output(vector<pair<ll,ll>> vec){ vector<int> ans; for(auto p : vec) ans.pb(p.S); answer(ans); } ll Sum(vector<pair<ll,ll>> vec){ ll sum=0; for(auto p : vec) sum+=p.F; return sum; } void solve(int n,int k,ll A,int S) { ll l=0,r=n+1; while(l+1<r){ ll mid=(l+r)>>1; if(skim(mid)<=A) l=mid; else r=mid; } vector<pair<ll,ll>> vec1,vec2; if(r<k){ impossible(); return ; } if(k<=l){ f(i,1,k+1) vec1.pb({skim(i),i}); f_(i,l,l-k+1) vec2.pb({skim(i),i}); if(Sum(vec1)<=2*A && A<=Sum(vec2)){ f(i,0,k+1){ vector<pair<ll,ll>> ans; f(j,0,i) ans.pb(vec1[j]); f(j,0,k-i) ans.pb(vec2[j]); if(A<=Sum(ans) && Sum(ans)<=2*A){ output(ans); return ; } } eror("FUCK"); } } if(k==r){ f(i,1,k) vec1.pb({skim(i),i}); } if(r<=n){ vector<int> ans; ll sum=0; ans.pb(r); sum+=skim(r); f(i,0,k-1) ans.pb(vec1[i].S),sum+=vec1[i].F; if(A<=sum && sum<=2*A){ answer(ans); return ; } } impossible(); } /* int32_t main(){ int n,k,A,S; cin>>n>>k>>A>>S; f(i,1,n+1) cin>>a[i]; solve(n,k,A,S); }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...