USACO 2019 December Contest Silver Division - Meetings

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can sort all cows, separate them by left/right, then calculate when the weight becomes less than half by sorting and looping through, then use queue to find the number intersections.

Source code

The source code in C++ can be seen below.

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

#define pii pair<int, int>
#define f first
#define s second

struct cow {
    int w, x, d;
};

int main() {
    freopen("meetings.in", "r", stdin);
    freopen("meetings.out", "w", stdout);

    int N, L; cin >> N >> L;

    vector<cow> cows(N);
    int total = 0;
    for(int i = 0; i < N; i++) {
        cin >> cows[i].w >> cows[i].x >> cows[i].d;
        total += cows[i].w;
    }

    sort(cows.begin(), cows.end(), [] (const cow &a, const cow &b){ return a.x < b.x;});

    vector<cow> left, right;
    for(auto c : cows){
        if(c.d == -1){
            left.push_back(c);
        }
        else{
            right.push_back(c);
        }
    }

    //cows never change direction, only weight

    vector<pii> weight_times;
    for(int i = 0; i < (int)left.size(); i++){
        weight_times.push_back({left[i].x, cows[i].w});
    }

    for(int i = 0; i < (int)right.size(); i++){
        weight_times.push_back({ L - right[i].x, cows[(int)left.size() + i].w });
    }

    sort(weight_times.begin(), weight_times.end(), [] (const pii &a, const pii &b){return a.f < b.f;} );

    int endTime = -1;
    for(pii c : weight_times){
        total -= 2 * c.s;
        if(total <= 0){
            endTime = c.f;
            break;
        } 
    }

    int ans = 0;
    queue<int> left_side;

    for(int i = 0; i < N; i++){
        if(cows[i].d == 1){
            left_side.push(cows[i].x);
        }
        else {
            while(!left_side.empty() && left_side.front() + 2 * endTime < cows[i].x ){
                left_side.pop();
            }
            ans += left_side.size();
        }
    }

    cout << ans;
}