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;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
#define fi first
#define se second
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int X = (int)2e4 + 4;
const int B = 10000 * 1ll * X + 1;
const ld EPS = 1e-5;
map<ll, ld> st;
ld Q(ll x){
if(!st.count(x)) st[x] = query(X, x);
return st[x];
}
ld g(ll x){
return Q(x) - Q(x - 1);
}
vector<int> aa, bb;
int n;
void go(ll l, ll r, ld gl, ld gr){
if(abs(gl-gr) < EPS) return;
if(aa.size() == n) return;
if(l + 1 == r){
int B = (l % X + X) % X;
if(B > (int)1e4) B = -(X - B);
int A = (l - B) / X;
aa.push_back(A);
bb.push_back(B);
return;
}
ll mid = l + (r - l) / 2ll;
ld gm = g(mid);
if((int)rng() % 2 == 0){
if(abs(gm-gl) > EPS){
go(l, mid, gl, gm);
}
if(abs(gm-gr) > EPS){
go(mid, r, gm, gr);
}
}
else{
if(abs(gm-gr) > EPS){
go(mid, r, gm, gr);
}
if(abs(gm-gl) > EPS){
go(l, mid, gl, gm);
}
}
}
void solve(int _id, int _n){
n = _n;
go(-B, +B, g(-B), g(+B));
the_lines_are(aa, bb);
}
Compilation message (stderr)
nicelines.cpp: In function 'void go(ll, ll, ld, ld)':
nicelines.cpp:39:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
39 | if(aa.size() == n) return;
| ~~~~~~~~~~^~~~
# | 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... |