| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 428021 | mosiashvililuka | A Difficult(y) Choice (BOI21_books) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
long long a,k,A,S,jm,f[100009],lef,rig,mid,i,j,ii,jj,zx,xc,F[100009];
deque <long long> de;
vector <int> vv;
/*int skim(int q){
return F[q];
}
void impossible(){
cout<<"-1";
}
void answer(vector <int> q){
for(int h=0; h<q.size(); h++){
cout<<q[h]<<" ";
}
}
vector <int> theend(){
vv.clear();
for(int h=0; h<de.size(); h++){
vv.push_back(de[h]);
}
return vv;
}*/
void solve(int N, int K, long long AA, int SS) {
a=N;k=K;A=AA;S=SS;
for(i=1; i<k; i++){
f[i]=skim(i);
de.push_back(i);
jm+=f[i];
}
f[k]=skim(k);
de.push_back(k);jm+=f[k];
if(jm>=A&&jm<=A*2){
answer(theend());
return;
}
if(jm>A*2){
impossible();
return;
}
jm-=f[k];de.pop_back();
lef=k;rig=a+1;
while(1){
if(lef+1>=rig){
mid=lef;
break;
}
mid=(lef+rig)/2;
f[mid]=skim(mid);
if(f[mid]+jm<=2*A){
lef=mid;
}else{
rig=mid;
}
}
if(jm+f[mid]>=A){
de.push_back(mid);
answer(theend());
return;
}
//cout<<"KL";
jm+=f[mid];de.push_front(mid);
i=mid;
for(j=k-1; j>=1; j--){
de.pop_back();jm-=f[j];
i--;f[i]=skim(i);jm+=f[i];de.push_front(i);
if(jm>=A){
answer(theend());
return;
}
}
impossible();
}
/*int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>k>>A>>S;
for(i=1; i<=a; i++){
cin>>F[i];
}
for(i=1; i<a; i++){
if(F[i+1]<=F[i]){
cout<<"NOT SORTED";
exit(0);
}
}
solve(a,k,A,S);
return 0;
}*/