| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 743189 | jamezzz | Viruses (BOI20_viruses) | C++17 | 0 ms | 0 KiB |
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>
using namespace std;
#include "nice_lines.h"
#define pf printf
#define pb push_back
#define maxn 10000
#define EPS 1e-5
#define dist(a,b,x,y) (ld)abs(y-a*x-b)/pow(1+a*a,0.5)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
map<ii,ld> memo;
vector<ii> know;
ld ask(ld x,ld y){
//ld res;
//if(memo.find({x,y})!=memo.end())res=memo[{x,y}];
//else res=memo[{x,y}]=query(x,y);
ld res=query(x,y);
for(auto[a,b]:know)res-=dist(a,b,x,y);
return res;
}
void solve(int subtask_id,int N){
ld far=ask(0,10001);
for(int i=0;i<N;++i){
int lo=-10000,hi=10000,mid,res;
while(lo<=hi){
mid=lo+((hi-lo)>>1);
if(ask(0,mid)>ask(0,mid+1))lo=mid+1;
else res=mid,hi=mid-1;
}
int b=(int)res;
lo=-10000,hi=10000;
while(lo<=hi){
mid=lo+((hi-lo)>>1);
if(ask(EPS,mid*EPS+b)>ask(EPS,(mid+1)*EPS+b))lo=mid+1;
else res=mid,hi=mid-1;
}
int a=(int)res;
know.push_back({a,b});
}
vector<int> A,B;
for(auto[a,b]:know)A.pb(a),B.pb(b);
the_lines_are(A,B);
}