Submission #411134

#TimeUsernameProblemLanguageResultExecution timeMemory
411134blacktulipA Difficult(y) Choice (BOI21_books)C++17
65 / 100
632 ms792 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long int lo; typedef pair<int,int> PII; #define fi first #define se second #define mp make_pair #define endl "\n" #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((bas+son)/2) const lo inf = 1000000000000000000; const lo KOK = 100000; const lo LOG = 30; const lo li = 500005; const lo mod = 1000000007; lo a[li],PS[li]; int cev; vector<int> v; void solve(int N, int K, long long A, int S) { lo sum=0; if(S==N){ for(int i=1;i<=N;i++){a[i]=skim(i);PS[i]=PS[i-1]+a[i];} for(int i=1;i<=N;i++){ if(i+K-1>N)break; lo at=0; for(int j=i;j<i+K;j++)at+=a[j]; int r=i+K-1; int flag=0; while(r<N && at<A){flag=1;at-=a[r];r++;at+=a[r];} if(at>=A && at<=2*A){ for(int j=i;j<i+K;j++)v.pb(j); v[K-1]=r; answer(v); } if(flag==0){ int l=i; while(l>1 && at>2*A){at-=a[l];l--;at+=a[l];} if(at>=A && at<=2*A){ for(int j=i;j<i+K;j++)v.pb(j); v[0]=l; answer(v); } } } impossible(); } //~ cout<<"***\n"; for(int i=N;i>=N-K+1;i--){ a[i]=skim(i); sum+=a[i]; v.pb(i); } //~ cout<<"***\n"; if(sum<A){impossible();} for(int i=0;i<(int)v.size();i++){ if(sum<=2*A)break; if(a[i+1]==0)a[i+1]=skim(i+1); if(sum-a[v[i]]+a[i+1]>=A){ sum-=a[v[i]]; v[i]=i+1; sum+=a[v[i]]; continue; } int bas=i+2; int son=N-K;; while(bas<=son){ //~ cout<<ort<<" :: "<<bas<<" :: "<<son<<endl; if(a[ort]==0)a[ort]=skim(ort); if(sum-a[v[i]]+a[ort]<A)bas=ort+1; else son=ort-1; } sum-=a[v[i]]; son=min(bas,N-K); if(a[bas]==0)a[bas]=skim(bas); sum+=a[bas]; v[i]=bas; } if(sum<A || sum>2*A)impossible(); else answer(v); }
#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...