Submission #530621

#TimeUsernameProblemLanguageResultExecution timeMemory
530621huangqrA Difficult(y) Choice (BOI21_books)C++14
0 / 100
1 ms200 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; // // --- Sample implementation for the task books --- // // To compile this program with the sample grader, place: // books.h books_sample.cpp sample_grader.cpp // in a single folder and run: // g++ books_sample.cpp sample_grader.cpp // in this folder. //#include<bits/stdc++.h> using namespace std; typedef long long ll; void solve(int N, int K, long long A, int S) { // TODO implement this function map<ll,ll>a; vector<int>ret; ll cur=0; for(int i=1;i<=K;i++)a[i]=skim(i),cur+=a[i]; if(cur >= A && cur <= 2*A){ for(int i=1;i<=K;i++)ret.push_back(i); answer(ret); } ll bound = N+1; a[N+1]=3e18; //inf for(int i=K;i>=1;i--){ cur -= a[i]; ll upper_add_limit = 2*A-cur; auto it = a.begin(); while(it->second <= upper_add_limit)it++; bound = min(bound,it->first); //Bound is now the index of the first exceeding known point /*cout<<"i: "<<i<<" upper_add_limit:"<<upper_add_limit<<"\n"; cout<<"i: "<<i<<" a:"; for(auto x:a)cout<<x.first<<"->"<<x.second<<" "; cout<<"\n"; cout<<"i: "<<i<<" bound:"<<bound<<"\n";*/ if(bound <= i+1)impossible(); it--; ll search_left = min(bound-1,it->first); ll search_right = bound-1; //[search_left, search_right] is the region where the last good point may be ll best = search_left; //cout<<"initially search_left: "<<search_left<<" search_right:"<<search_right<<"\n"; assert(it->second <= upper_add_limit); assert(search_left >= i); assert(search_right >= i+1); assert(search_left <= search_right); while(search_left <= search_right){ cout<<"search_left: "<<search_left<<" search_right:"<<search_right<<"\n"; ll mid = (search_left+search_right)/2; ll x; if(a.find(mid)!=a.end())x=a[mid]; else x=a[mid]=skim(mid); if(x <= upper_add_limit){ best = search_left; search_left = mid+1; } else search_right = mid-1; } //assert(search_left == search_right); bound = best; cur += a[bound]; ret.push_back(bound); if(cur >= A && cur <= 2*A){ for(int j=1;j<=i-1;j++)ret.push_back(j); answer(ret); } //The hard part! The binary search /*auto pos = upper_bound(a.begin()+i+1,a.begin()+bound,2*A-cur); if(pos==a.begin()+i+1)impossible(); pos--; bound = pos - a.begin();*/ } impossible(); }
#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...