Submission #750947

#	Time	Username	Problem	Language	Result	Execution time	Memory
750947		doowey	Nicelines (RMI20_nicelines)	C++17	85.82 / 100	61 ms	304 KiB

nicelines

#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

const int X = (int)2e4 + 4;
const int B = 10000 * 1ll * X + 1;
const ld EPS = 1e-5;

ld g(ll x){
    return query(X, x) - query(X, x - 1);
}


vector<int> aa, bb;


void go(ll l, ll r, ld gl, ld gr){
    if(abs(gl-gr) < EPS)  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(abs(gm-gl) > EPS){
        go(l, mid, gl, gm);
    }
    if(abs(gm-gr) > EPS){
        go(mid, r, gm, gr);
    }
}

void solve(int _id, int _n){
    go(-B, +B, g(-B), g(+B));
    the_lines_are(aa, bb);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 14.5435715783 / 19
• Subtask 5: 21.2588247555 / 23
• Subtask 6: 19.0130860602 / 27