USACO 2020 December Contest Silver Division - Stuck in a Rut

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Sort east cows and north cows to check which one blocks which, and then we only have to do some casework for each of them.

Source code

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

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

struct cow {
    int x, y, id;
};

bool comp(cow a, cow b) { 
    return a.y < b.y; 
}

bool comp1(cow a, cow b) { 
    return a.x < b.x;
}

int main() {
    int N;
    cin >> N;

    vector<cow> ec, nc;

    for (int i = 0; i < N; i++) {
        char type;
        cin >> type;
        int x, y;
        cin >> x >> y;

        if (type == 'E') {
            ec.push_back({x, y, i});
        } 
        else {
            nc.push_back({x, y, i});
        }
    }

    sort(ec.begin(), ec.end(), comp);
    sort(nc.begin(), nc.end(), comp1);

    vector<int> ans(N, 0);
    vector<bool> stopped(N, false);
    for (cow i : ec) {
        for (cow j : nc) {
            if (!stopped[i.id] && !stopped[j.id] && i.x <= j.x && i.y >= j.y) {
                int xd = (j.x - i.x), yd = (i.y - j.y);

                if (xd == yd) {
                    continue;
                }

                if (xd < yd) {
                    stopped[j.id] = true;
                    ans[i.id] += (1 + ans[j.id]);
                } 
                else {
                    stopped[i.id] = true;
                    ans[j.id] += (1 + ans[i.id]);
                }
            }
        }
    }

    for (int i = 0; i < N; i++) {
        cout << ans[i] << "\n";
    }
}