Submission #376010

#	Time	Username	Problem	Language	Result	Execution time	Memory
376010		Aldas25	Wish (LMIO19_noras)	C++14	100 / 100	749 ms	15596 KiB

noras

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 500100, MAXK = 23;
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ld PI = asin(1) * 2;

void setIO () {
    FAST_IO;
}

void setIO (string s) {
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int n;
ll r;
ll a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll dx[MAXN], dy[MAXN];

pair<ld, ld> getPos (int i, ld t) {
    ld x = ((ld)a[i]) + ((ld)dx[i]) * t;
    ld y = ((ld)b[i]) + ((ld)dy[i]) * t;
    return {x,y};
}

ld getOptTime (int i) {
    ld le = 0.0, ri = 1e8+1;

    while (ri-le > 1e-2) {
        ld mid1 = le + (ri-le)/3;
        ld mid2 = ri - (ri-le)/3;

        auto pos1 = getPos(i, mid1);
        auto pos2 = getPos(i, mid2);

        if (pos1.f < -1e9 || pos1.f > 1e9 || pos1.s < -1e9 || pos1.s > 1e9)
            ri = mid1;
        else if (pos2.f < -1e9 || pos2.f > 1e9 || pos2.s < -1e9 || pos2.s > 1e9)
            ri = mid2;
        else {
            ld d1 = pos1.f * pos1.f + pos1.s * pos1.s;
            ld d2 = pos2.f * pos2.f + pos2.s * pos2.s;
            if (d1 < d2) ri = mid2;
            else le = mid1;
        }
    }

    return le;
}

bool canReach (int i, ll t) {
    if (t < 0) return false;
    ll x = a[i] + dx[i] * t;
    ll y = b[i] + dy[i] * t;

    if (x < -r || x > r || y < -r || y > r)
        return false;

    ll d = x*x + y*y;
    return d <= r*r;
}

ll getFrBounds (int i, ll t) {
    ll le = 0;
    ll ri;
    if (canReach(i, t+1)) ri = t+1;
    else if (canReach(i, t)) ri = t;
    else if (canReach(i, t-1)) ri = t-1;
    else return -1;

    while (le < ri) {
        ll mid = (le+ri)/2;
        if (canReach(i, mid)) ri = mid;
        else le = mid+1;
    }

    return le;
}

ll getToBounds (int i, ll t) {
    ll ri = 1e8+1;
    ll le;
    if (canReach(i, t-1)) le = t-1;
    else if (canReach(i, t)) le = t;
    else if (canReach(i, t+1)) le = t-1;
    else return -1;

    while (le < ri) {
        ll mid = (le+ri+1)/2;
        if (canReach(i, mid)) le = mid;
        else ri = mid-1;
    }

    return le;
}

map<ll, int> cnt;

int main() {
	setIO();

    cin >> n >> r;
    FOR(i,1, n) cin >> a[i] >> b[i] >> c[i] >> d[i];
    FOR(i, 1, n) dx[i] = c[i] - a[i], dy[i] = d[i] - b[i];

    FOR(i, 1, n) {
        ld t = getOptTime (i);
       // cout << " i = " << i << " t= " << t << endl;

        ll tt = round(t);
      //  cout << " tt = " << tt << endl;

        ll fr = getFrBounds (i, tt);
        ll to = getToBounds (i, tt);

        //cout << " fr = " << fr << " to  = " << to << endl;

        if (fr <= to) {
            cnt[fr]++;
            cnt[to+1]--;
        }
    }

    int ans = 0;
    int cur = 0;
    for (auto p : cnt) {
        cur += p.s;
        if (p.f >= 0)
            ans = max(ans, cur);
    }
    cout << ans << "\n";

	return 0;
}

Compilation message (stderr)

noras.cpp: In function 'void setIO(std::string)':
noras.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
noras.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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