Cereal 2 (C++11)

Falin Yu (lisayu999)
Submitted: Mon, Jan 31, 2022 01:54:22 EST
Contest: USACO 2022 January Contest, Silver

// jan. problem 3
#include <bits/stdc++.h>
using namespace std;

template <typename T> vector<T> concat(vector<T> &v1, vector<T> &v2) {
    vector<T> n = vector<T>();
    copy(v1.begin(), v1.end(), back_inserter(n));
    copy(v2.begin(), v2.end(), back_inserter(n));
    return n;
}
struct Cow
{
    int p1;   // first favorite
    int p2;   // second favorite
    int idx;  // keeping index for output
    bool operator<(const Cow &c) {
        if(p1!=c.p1)
            return p1 < c.p1;
        if(p2!=c.p2)
            return p2 < c.p2;
        return idx < c.idx;
    }
};

void dump(vector<Cow> &v) {
    for(auto x:v) {
        cout << "(" <<x.p1<<","<<x.p2<<","<<x.idx<<") ";
    }
    cout << endl;
}

#define MAXCONV 100

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N,M;
    map<int,int> cnt;
    cin >> N >> M;

    vector<Cow> cows(N);
    for(int i=0; i<N; i++) {
        cin >> cows[i].p1 >> cows[i].p2;
        cows[i].idx = i+1;
        cnt[cows[i].p1]=1;
        cnt[cows[i].p2]=1;
    }
    int real=cnt.size();
    // cout << "real:" << real << endl;
    int maxmin=(N-real)>0 ? N-real:0;
    sort(cows.begin(), cows.end());

    // for(auto x:cows) {
    //     cout << x.p1 << " " << x.p2 << " " << x.idx << endl;
    // }
    int hungries = -1;
    int convergence = 0;
    // greedy convergence approach to put unfilled cows to first
    for(;;){
        vector<int> occ(M+1,0);
        vector<Cow> filled, unfilled;
        // dump(cows);
        int unfilled_num = 0;
        for(auto x:cows) {
            if(!occ[x.p1]) {
                occ[x.p1] = 1;
                filled.push_back(x);
            } else {
                if(!occ[x.p2]) {
                    occ[x.p2] = 1;
                    filled.push_back(x);
                }
                else {
                    unfilled.push_back(x);
                    unfilled_num++;
                }
            }
        }
        if(unfilled_num != hungries) {
            hungries = unfilled_num;
            convergence = 0;
        } else {
            convergence ++;
        }
        if(convergence>MAXCONV) break;
        // already reached max minumum
        if(hungries==maxmin) break;
        
        // merge(unfilled.begin(), unfilled.end(), filled.begin(), filled.end(), cows.begin());
        cows=concat(unfilled, filled);
        
    }
    cout << hungries << endl;
    
    for(int i=0; i<N; i++) {
        cout << cows[i].idx << endl;
    }
     
}