Submission #592573

#TimeUsernameProblemLanguageResultExecution timeMemory
592573dantoh000Nicelines (RMI20_nicelines)C++14
100 / 100
12 ms600 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #include "nice_lines.h" map<ll, map<ll, ld> > cache; ld Q(ll x, ll y){ if (cache[x].count(y)) return cache[x][y]; else return cache[x][y] = query((ld)x, (ld)y); } ld getdiff(ll x, ll y){ return Q(x, y+1) - Q(x, y); } vector<ll> ans; vector<ld> diffs; ll X = 20001; void dnc(ll L, ll R, ld S, ld E){ if (abs(S-E) < 1e-5){ return; } ///printf("DNC %lld %lld %.20Lf %.20Lf, %.20Lf\n",L,R,S,E, E-S); if (L >= R) return; for (auto x : diffs){ if (abs(E-S-x) < 3e-11){ ///printf("FOUND %.20Lf %.20Lf = %.20Lf\n",S,E,E-S-x); long double difff = Q(X, R) - Q(X, L) - (R-L)*S; long double idx = difff/x; ///printf("%Lf diffs\n", idx); ans.push_back(R-(int)round(idx)); return; } } if (L+1 == R){ ans.push_back(L+1); return; } ll mid = (L+R)/2; ld Q = getdiff(X, mid); dnc(L, mid, S, Q); dnc(mid, R, Q, E); } void solve(int subtask_id, int N) { ///printf("subtask_id = %d, N = %d\n", subtask_id, N); ll L = -10000*X - 10000 - 1; ll R = 10000*X + 10000 + 1; for (ll i = 0; i <= 10000; i++){ long double D = (ld)(2.0)/sqrtl(i*i + 1); ///printf("%.20Lf\n",D); diffs.push_back(D); } long double Q1 = getdiff(X, L); long double Q2 = getdiff(X, R); dnc(L, R, Q1, Q2); vector<int> a,b; for (auto x : ans){ ///printf("%lld\n",x); int A = round((ld)x/X); int B = x - A*X; a.push_back(A); b.push_back(B); } the_lines_are(a,b); }
#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...