Help on Cow-libi, silve Feb. 2023

Problems and Contests
#1

Following the posted idea on usaco.org, I implemented the following code to solve the problem Cow-libi, silver Feb. 2023. (problem: USACO)

However, my solution can only solve test case 1 - 4. It shows wrong for cases 5-11.

I downloaded the test data and tried test cases 5 and 6. My output undercounts.

I would appreciate it someone can tell me what is wrong with my solution.

My code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct info {
    long long x;
    long long y;
    long long t;
};

bool cmp(const info& x, const info& y)
{
    return x.t < y.t;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int G, N;
    long long a, b, c;
    int ans = 0;
    int count;

    vector<info> grazings;
    vector<long long> times;

    cin >> G >> N;

    for(int i = 0; i < G; i++) {
        cin >> a >> b >> c;

        grazings.push_back({a, b, c});
    }

    sort(grazings.begin(), grazings.end(), cmp);

    for(int i = 0; i < G; i++) {
        times.push_back(grazings[i].t);
    }

    for(int i = 0; i < N; i++) {
        cin >> a >> b >> c;

        auto it = lower_bound(times.begin(), times.end(), c);
        int idx = it - times.begin();

        for(int j = idx - 1; j <= idx; j++) {
            if(j >= 0 && j < G) {
                if(pow(grazings[j].x - a, 2) + pow(grazings[j].y - b, 2) > pow(grazings[j].t - c, 2)) {
                    ans++;
                    break;
                }
            }
        }
    }

    cout << ans << endl;
    
    return 0;
}
#2

pow converts its arguments to doubles, resulting in a loss of precision.

1 Like
#3

So does sqrt, but that isn’t needed anyways. My solution now passes all but the second test case!