Submission #750977

#	Time	Username	Problem	Language	Result	Execution time	Memory
750977		doowey	Nicelines (RMI20_nicelines)	C++14	100 / 100	11 ms	720 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

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-11;

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;
vector<ld> diff;

int n;

void go(ll l, ll r, ld gl, ld gr){
    if(abs(gl-gr) < 1e-8)  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;
    }
    for(auto x : diff){
        if(abs(gr - x - gl) < 5e-11){
            ld kk = (Q(l) - Q(r) + gr * r - gl * l) / (gr-gl);
            ll p = round(kk);
            int B = (p % X + X) % X;
            if(B > (int)1e4) B = -(X - B);
            int A = (p - 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) > 1e-8){
            go(l, mid, gl, gm);
        }
        if(abs(gm-gr) > 1e-8){
            go(mid, r, gm, gr);
        }
    }
    else{
        if(abs(gm-gr) > 1e-8){
            go(mid, r, gm, gr);
        }
        if(abs(gm-gl) > 1e-8){
            go(l, mid, gl, gm);
        }
    }
}

void solve(int _id, int _n){
    n = _n;
    for(int i = 0 ; i <= 10000; i ++ ){
        ld dd = 2.0 / sqrt(i * i + 1.0);
        diff.push_back(dd);
    }
    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:40:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if(aa.size() == n) return;
      |        ~~~~~~~~~~^~~~

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