Submission #377214

#	Time	Username	Problem	Language	Result	Execution time	Memory
377214		gustason	Wish (LMIO19_noras)	C++14	0 / 100	10 ms	468 KiB

noras

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
int INF = 1e9 + 5;
int n, r;
vector<pair<int, int>> a;
vector<pair<int, int>> dir;
vector<int> best;
vector<pair<int, int>> fr;
bool inside(int x, int y) {
    if (x == r && y == 0) return true;
    if (x == -r && y == 0) return true;
    if (x == 0 && y == r) return true;
    if (x == 0 && y == -r) return true;
    int rr = r;
    if (x >= -(rr-1) && x <= (rr-1) && y >= -(rr-1) && y <= (rr-1)) return true;
    return false;
}
int getP(int x, int x0, int d) {
    int ans = ceil((ld) ((ld) x - (ld) x0) / (ld) d);
    if (ans < 0) return -1;
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    map<int, int> mp;
    cin >> n >> r;
    a.resize(n);
    dir.resize(n);
    best.assign(n, INF);
    fr.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
        cin >> dir[i].first >> dir[i].second;
        dir[i] = {dir[i].first - a[i].first, dir[i].second - a[i].second};
//        cout << a[i].first << " " << a[i].second << " ";
//        cout << dir[i].first << " " << dir[i].second << "\n";
    } cerr << "\n";

    vector<pair<int, int>> ps = {
    {r, r}, {-r, -r}, {(r-1), (r-1)}, {-(r-1), -(r-1)}, {0, 0}
    };
    for(int i = 0; i < n; i++) {
        if (inside(a[i].first, a[i].second)) {
            best[i] = 0;
            fr[i] = a[i];
            continue;
        }
        for(pair<int, int> j : ps) {
            int mov = getP(j.first, a[i].first, dir[i].first);
//            cout << j.first << " " << a[i].first << " " << dir[i].first << " " << mov << "\n";
//            cout << a[i].first + mov * dir[i].first << " " << a[i].second + mov * dir[i].second << "\n";
            if (mov != -1) {
                if (inside(a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second)) {

                    if (mov < best[i]) {
                        best[i] = mov;
                        fr[i] = {a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second};
                    }
                }
            }
            mov = getP(j.second, a[i].second, dir[i].second);
            if (mov != -1) {
                if (inside(a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second)) {
                    if (mov < best[i]) {
                        best[i] = mov;
                        fr[i] = {a[i].first + mov * dir[i].first, a[i].second + mov * dir[i].second};
                    }
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        int L = best[i], R = INF, ans = INF;
        while(L <= R) {
            int mid = (L + R) / 2;
            if (dir[i].first != 0 && mid >= abs(INF / dir[i].first)) {
                R = mid - 1;
                ans = mid;
                continue;
            }
            if (dir[i].second != 0 && mid >= abs(INF / dir[i].second)) {
                R = mid - 1;
                ans = mid;
                continue;
            }
            if (inside(a[i].first + mid * dir[i].first, a[i].second + mid * dir[i].second)) {
                L = mid + 1;
            } else {
                R = mid - 1;
                ans = mid;
            }
        }
        cerr << best[i] << " " << ans << "\n";
        mp[best[i]]++;
        mp[ans]--;
    }

    int ans = 0, curr = 0;
    for(auto i : mp) {
        if (i.first >= INF) break;
        curr += i.second;
        ans = max(ans, curr);
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 23
• Subtask 3: 0 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7