Submission #1240905

#TimeUsernameProblemLanguageResultExecution timeMemory
1240905KindaGoodGamesA Difficult(y) Choice (BOI21_books)C++20
0 / 100
3 ms1196 KiB
#include <bits/stdc++.h> #include "books.h" #define tiii tuple<int,int,int> #define int long long using namespace std; vector<int> arr; struct cmp{ int ind; cmp(int i){ ind = i; } bool operator<(const cmp a) const{ return ind < a.ind; } // bool operator<(const int a) const{ // return arr[ind] < a; // } }; void solve(int32_t n, int32_t K, long long A, int32_t S) { arr.resize(n,-1); for(int i = 0; i < n; i++){ arr[i] = skim(i+1); } vector<int32_t> chose(K); int sum = 0; for(int i = 0; i < K; i++){ chose[i] = i; sum += arr[i]; } if(sum > 2*A) { impossible(); } priority_queue<tiii> pq; set<cmp> av; for(int i = K; i < n; i++){ av.insert(cmp(i)); } for(int i = 0; i < K; i++){ // reevaluate tiii choice = {-1,i,-1}; int bound = (2*A)-sum+arr[chose[i]]; auto it = (av.upper_bound(bound)); if(it == av.begin())continue; it--; int j = (*it).ind; int del = -arr[chose[i]]+arr[j]; // assert(sum <= 2*A); if(del <= 0) continue; choice = max(choice, {del, i, j}); pq.push(choice); } while(pq.size() && sum < A){ int delta, old, nxt; tie(delta,old,nxt) = pq.top(); pq.pop(); if(arr[nxt]-arr[chose[old]] != delta || find(chose.begin(),chose.end(),nxt) != chose.end()){ // reevaluate tiii choice = {-1,old,-1}; int bound = (2*A)-sum+arr[chose[old]]; auto it = av.upper_bound(bound); if(it == av.begin())continue; it--; int j = (*it).ind; int del = arr[j]-arr[chose[old]]; // assert(sum <= 2*A); if(del <= 0) continue; choice = max(choice, {del, old, j}); pq.push(choice); continue; } if(sum+delta > 2*A) { continue; } int oind = chose[old]; chose[old] = nxt; sum += delta; av.insert(oind); av.erase(nxt); // this element may be reinserted tiii choice = {-1,old,-1}; int bound = (2*A)-sum+arr[chose[old]]; auto it = av.upper_bound(bound); if(it == av.begin())continue; it--; int j = (*it).ind; int del = arr[j]-arr[chose[old]]; // assert(sum <= 2*A); if(del <= 0) continue; choice = max(choice, {del, old, j}); pq.push(choice); } if(sum < A){ impossible(); }else{ for(int i = 0; i < K; i++) chose[i]++; answer(chose); } }
#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...