Submission #944437

#TimeUsernameProblemLanguageResultExecution timeMemory
944437daoquanglinh2007Nicelines (RMI20_nicelines)C++17
77.76 / 100
43 ms708 KiB
#include <bits/stdc++.h> #include "nice_lines.h" using namespace std; #define ll long long #define ld long double #define pii pair <int, int> #define fi first #define se second #define mp make_pair const ll LIM = 1e4, x0 = 2*LIM, MAX_DEP = 32; const ld EPS = 1e-9, inf = 1e18; vector <int> va, vb; set <pii> S; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void get(ld y){ int b = int(round(y+x0*LIM+LIM))%x0-LIM, a = int(round(y-b)/(ld)x0); if (!S.count(mp(a, b))){ va.push_back(a); vb.push_back(b); S.insert(mp(a, b)); } } void dnc(int dep, ld l, ld r, ld fl, ld fr){ if (dep == MAX_DEP){ get((l+r)/2.0); return; } ld mid = (l+r)/2.0; if (fl == +inf) fl = query(x0, l); if (fr == +inf) fr = query(x0, r); ld fmid = query(x0, mid); if (abs(2.0*fmid - (fl+fr)) <= EPS) return; dnc(dep+1, l, mid, fl, fmid); dnc(dep+1, mid, r, fmid, fr); } void solve(int subtask_id, int N){ va.clear(); vb.clear(); dnc(0, -2*LIM*(x0+1), 2*LIM*(x0+1), +inf, +inf); the_lines_are(va, vb); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...