I was solving this problem: there are k interviewers and n cows (3*10^5 \ge n \ge k \ge 1) the interviewers will start processing cows from 1 to k at time 0 and when they finish they will start interviewing the next cow. If x interviewers finish at the same time each one will choose randomly one of the next x cows to interview, you need to output the time when bessie will be interviewed (she is cow n+1) and the possible interviewers that can interview her.
I used a dsu to solve this problem, I simulated the problem and when 2 or more interviewers finished at the same time I joined their sets (since the next cow are chosen randomly and we want to know if there is a possibility that one of these interviewers will interview Bessie). I think this solution is actually really similar to solution 1 from the editorial but unfortunatly it passes only the first 9 testcases.
I actually checked my code multiple times and it doesn’t seem to me that I made errors in implementing this idea, but how can this be different from solution 1 of the editorial?
here’s my code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,x) for(int i=(j);i<(x);i++)
#define f first
#define s second
using ll = long long;
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
rep(i,0,t){
solve();
}
}
int parent[300000];
int siz[300000];
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void make_set(int v) {
parent[v] = v;
siz[v] = 1;
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] < siz[b])
swap(a, b);
parent[b] = a;
siz[a] += siz[b];
}
}
void solve(){
int n,k;
cin>>n>>k;
rep(i,0,k)make_set(i);
vector<ll> arr(n);
rep(i,0,n)cin>>arr[i];
priority_queue<pair<ll,ll>> pq;
rep(i,0,k)pq.push({-arr[i],i});
int next = k;
while(!pq.empty()){
vector<pair<ll,ll>> cur = {pq.top()};
ll time = cur[0].f;
pq.pop();
while(!pq.empty() && pq.top().f == cur.back().f){
cur.push_back(pq.top());
pq.pop();
}
rep(i,1,cur.size())union_sets(cur[0].s,cur[i].s);
rep(i,0,cur.size()){
if(next==n){
cout<<-cur[i].f<<'\n';
rep(j,0,k)cout<< (find_set(j)==find_set(cur[0].s) ? 1 : 0);
cout<<'\n';
return;
}
pq.push({cur[i].f - arr[next++],cur[i].s});
}
}
}