oj.uz

Submission #750977

# Submission time Handle Problem Language Result Execution time Memory
750977 2023-05-30T17:25:54 Z doowey Nicelines (RMI20_nicelines) C++14
100 / 100
 11 ms 720 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 1 ms 592 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 592 KB Output is correct
2 Correct 7 ms 592 KB Output is correct
3 Correct 7 ms 592 KB Output is correct
4 Correct 8 ms 592 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 4 ms 592 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 592 KB Output is correct
2 Correct 7 ms 592 KB Output is correct
3 Correct 7 ms 592 KB Output is correct
4 Correct 8 ms 592 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 10 ms 592 KB Output is correct
10 Correct 9 ms 592 KB Output is correct
11 Correct 9 ms 592 KB Output is correct
12 Correct 11 ms 592 KB Output is correct