This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "nice_lines.h"
using namespace std;
#define ld long double
map<int,map<int,ld>> mp;
const int V=10000;
const int X=20001;
ld get(int x,int y){
if(mp[x].find(y)!=mp[x].end()) return mp[x][y];
else return mp[x][y]=query((ld)x,(ld)y);
}
ld get_slope(int x,int y){
return get(x,y+1)-get(x,y);
}
vector<ld> d;
vector<int> ans;
void dnc(int L,int R,ld sL,ld sR){
if(abs(sR-sL)<1e-5 || L>=R) return;
for(ld x:d){
if(abs(sR-sL-x)<3e-11){
ld dif=get(X,R)-get(X,L)-(R-L)*sL;
ld idx=dif/x;
ans.push_back(R-(int)round(idx));
return;
}
}
if(L+1==R){
ans.push_back(R);
return;
}
int M=(L+R)>>1;
dnc(L,M,sL,get_slope(X,M));
dnc(M,R,get_slope(X,M),sR);
}
void solve(int subtask_id,int N){
int R=V*X+V+1,L=-R;
for(int i=0;i<=V;i++) d.push_back((ld)(2.0)/sqrtl(i*i+1));
dnc(L,R,get_slope(X,L),get_slope(X,R));
vector<int> a,b;
for(auto x:ans){
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |