| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 568527 | CSQ31 | The Collection Game (BOI21_swaps) | C++17 | 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 "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
vector<pii>r;
void init(int N, int A[], int B[]) {
n = N;
for(int i=0;i<n;i++)r.push_back({A[i],B[i]});
sort(r.begin(),r.end());
}
int can(int m, int K[]) {
int sum = 0;
map<int,int>cnt;
for(int i=0;i<m;i++){
sum+=K[i];
cnt[K[i]]++;
if(sum>n)return 0;
}
vector<pii>a;
for(auto x:cnt)a.push_back(x);
int s = a.size();
vector<int>need(s,0);
assert(s<=450);
for(int i=0;i<s;i++)need[i] = a[i].fi * a[i].se;
int ptr = -1;
multiset<int>w;
for(int i=0;i<s;i++){
int last = ptr;
while(ptr+1<n && r[ptr+1].fi<=a[i].fi)ptr++;
//cout<<last<<" "<<ptr<<'\n';
for(int j=last+1;j<=ptr;j++)w.insert(r[j].se);
while(!w.empty() && *w.begin() < a[i].fi)w.erase(w.begin());
while(!w.empty() && need[i]){
w.erase(w.begin());
need[i]--;
}
}
for(int x:need)cout<<x<<" ";
for(int x:need){
if(x)return 0;
}
return 1;
}