# Why did the cow cross the road?

## Problem Info

Why did the cow cross the road?
(USACO)

## My Work

``````#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;
using ll = long long;

/*#define f first
#define s second*/
#define FOR(i,n) for(int i=0;i<(int)(n);i++)
#define vec vector<int>
#define pb push_back
#define pi pair<int, int>
#define nl '\n'

void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
if(name.length()) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}

struct Cow {
int s, f, r, sreach, freach;
} cows[20000];

int C, N;
int cvals[20000];
bool taken[20000];

int main() {
setIO("helpcross");
cin >> C >> N;
FOR(i, C)
cin >> cvals[i];
FOR(i, N)
cin >> cows[i].s >> cows[i].f;
sort(cvals, cvals + C);

FOR(i, N) {
int *begin = lower_bound(cvals, cvals + C, cows[i].f), *end = lower_bound(cvals, cvals + C, cows[i].s);
int amount = begin - end;
cows[i].r = amount;
cows[i].sreach = end - cvals;
cows[i].freach = begin - cvals;
}

sort(cows, cows + N, [](Cow a, Cow b){
return a.f < b.f; // sort based on ending time
});
int gotten = 0;
FOR(i, N) {
for (int j = cows[i].sreach; j < C && j < cows[i].freach; j++) {
if (!taken[j]) {
taken[j] = true;
gotten++;
break;
}
}
}
cout << gotten << nl;
}

``````

Add explanation of code here
I take the earliest-finishing cow and match that first and then so on. I believe that I am off by one on test case 5, but I don’t know why.

## What I’ve Tried

I downloaded the test data and ran it on my computer

## Question

Why does this not work on test case 5 but on all other test cases it does work?

• We expect that you have already tried generating small counter-tests (as described in the module) but you haven’t found one that your program fails on. Include the generator code.

Have you tried this?