oj.uz

Submission #750952

# Submission time Handle Problem Language Result Execution time Memory
750952 2023-05-30T16:36:47 Z doowey Nicelines (RMI20_nicelines) C++14
86.7093 / 100
 73 ms 680 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-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

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;
      |        ~~~~~~~~~~^~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
14.8608981042 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 512 KB Output is partially correct
2 Partially correct 56 ms 456 KB Output is partially correct
3 Partially correct 56 ms 476 KB Output is partially correct
4 Partially correct 57 ms 548 KB Output is partially correct

Subtask #5
21.3745676187 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 336 KB Output is partially correct
2 Partially correct 16 ms 336 KB Output is partially correct
3 Partially correct 19 ms 336 KB Output is partially correct
4 Partially correct 21 ms 364 KB Output is partially correct

Subtask #6
19.473869556 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 48 ms 512 KB Output is partially correct
2 Partially correct 56 ms 456 KB Output is partially correct
3 Partially correct 56 ms 476 KB Output is partially correct
4 Partially correct 57 ms 548 KB Output is partially correct
5 Partially correct 16 ms 336 KB Output is partially correct
6 Partially correct 16 ms 336 KB Output is partially correct
7 Partially correct 19 ms 336 KB Output is partially correct
8 Partially correct 21 ms 364 KB Output is partially correct
9 Partially correct 61 ms 680 KB Output is partially correct
10 Partially correct 66 ms 624 KB Output is partially correct
11 Partially correct 73 ms 540 KB Output is partially correct
12 Partially correct 53 ms 548 KB Output is partially correct