p188.ans1
======================
2 1 1


=================
p188.in1
======================
3 2
0 1 2
1 -1 -2

=================
statement.txt
======================
188. Factory guard
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



The fence around the strategically important Berland pistachio factory has a circle form. N soldiers were posted to guard the factory according to the new government program "Pistachio protection in industry and life" (decree 1731 of 10/10/2003). Each soldier moves along the outer side of the fence at a constant speed (clockwise or counter-clockwise). The fence perimeter is 1000 meters long. The initial position of each soldier Li (the distance from the entrance checkpoint round the circle clockwise) is known, 0<=Li<=999, all Li are different integers. The speed of each soldier is Vi meters per minute (-100<=Vi<=100, Vi<>0, Vi is integer). Note: if a soldier's speed is negative, then he moves in the counter-clockwise direction, and in the clockwise direction in the opposite case.
If a soldier meets another soldier on his way, he immediately asks him a password "Have you a spare cigarette?", and getting a "No" answer he keeps on moving. Note, the term "meet" means the moment of time, when the two soldiers are at one and the same point with the opposite velocities. Since the soldiers serve for over a year they have learned to say the password and the answer so quickly, that if a soldier meets several soldiers at once, he manages both to ask each soldier for a password and to answer him.
Your task is to find out how many times each soldier asks a password during the period of T minutes from the initial moment of time (inclusive).

Input
The first line contains two natural numbers N and T (1<=N<=20; 1<=T<=50). The second line contains integer numbers L1, L2, ..., LN, and the third line contains V1, V2, ..., VN. Numbers in each line are separated by one or more spaces.

Output
Output N numbers B1, B2, ..., BN separated by a space, where Bi is the number of questions asked by the i-th soldier.

Sample test(s)

Input
3 2
0 1 2
1 -1 -2

Output
2 1 1
Author:	Michael R. Mirzayanov
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9








=================
p188.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, t;
vector<int> l, v;

void read() {
    cin >> n >> t;
    l.resize(n);
    v.resize(n);
    cin >> l >> v;
}

int64_t first_c_geq(int64_t val) {
    if(val >= 0) {
        return (val + 999) / 1000;
    }
    return -((-val) / 1000);
}

int64_t last_c_leq(int64_t val) {
    if(val >= 0) {
        return val / 1000;
    }
    return -((-val + 999) / 1000);
}

int64_t count_meetings(int l1, int v1, int l2, int v2) {
    if((v1 > 0) == (v2 > 0)) {
        return 0;
    }

    int64_t dv = v1 - v2;
    int64_t dl = l2 - l1;

    int64_t c_low, c_high;
    if(dv > 0) {
        c_low = first_c_geq(-dl + 1);
        c_high = last_c_leq(dv * t - dl);
    } else {
        c_low = first_c_geq(dv * t - dl);
        c_high = last_c_leq(-dl - 1);
    }

    if(c_high < c_low) {
        return 0;
    }
    return c_high - c_low + 1;
}

void solve() {
    // Instead of having a circle, we can think of this as a plane with lines y
    // = Vi * t + Li for each of the soldiers. We will simply just make an
    // infinite number of copies starting at Li, Li + 1000, Li + 2000 and so on
    // (also same for negatives). Let's figure out how many intersections there
    // would be between each pair of lines. We know the form of one line is y =
    // Vi * t + Li, while we can consider all the lines y = Vi * t + Li + 1000 *
    // c. Particularly, we can binary search on c to figure out the first t > 0
    // and the last integer t <= T, or alternatively just do some simple math.
    // The answer being the length of this interval. The time complexity will be
    // O(N^2).

    vector<int64_t> ans(n, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                ans[i] += count_meetings(l[i], v[i], l[j], v[j]);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        cout << ans[i];
        if(i < n - 1) {
            cout << ' ';
        }
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
