Submission #942853

#	Time	Username	Problem	Language	Result	Execution time	Memory
942853		Pannda	Nicelines (RMI20_nicelines)	C++17	67.14 / 100	35 ms	2024 KiB

nicelines

#include "nice_lines.h"

#include <bits/stdc++.h>
using namespace std;

void solve(int subtask_id, int n) {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    auto rand = [&](int l, int r) { return uniform_int_distribution<int>(l, r - 1)(rng); };
    const long double EPS = 1e-8;
    const int CL = -10000, CR = 10000;

    auto [a, b] = [&]() -> pair<vector<int>, vector<int>> {
        map<array<long long, 2>, long double> memorize;
        auto subquery = [&](long long x, long long y) {
            if (memorize.count({x, y})) return memorize[{x, y}];
            return memorize[{x, y}] = query(x, y);
        };
        auto f = [&](long long x, long long y) {
            return subquery(x, y + 1) - subquery(x, y);
        };
        vector<int> a, b;
        long long x = rand(20, 50);
        long long last = -5.1e5;
        for (int i = 0; i < n; i++) {
            long long l = last + 1, r = 5.1e5;
            while (l < r) {
                long long m = (l + r) >> 1;
                if (abs(f(x, m) - f(x, last)) > EPS) r = m;
                else l = m + 1;
            }
            long long y = l;
            long double d = abs(f(x, y) - f(x, last)) / 2;
            int _a = round(sqrt(1.0 / d / d - 1.0));
            int c = rand(1, 10);
            if (abs(f(x + c, y + c * _a) - f(x + c, y + c * _a - 1)) < EPS) _a *= -1;
            int _b = y - _a * x;
            a.push_back(_a);
            b.push_back(_b);
            last = y;
        }
        return make_pair(a, b);
    }();

    the_lines_are(a, b);
}

Compilation message (stderr)

nicelines.cpp: In function 'void solve(int, int)':
nicelines.cpp:10:15: warning: unused variable 'CL' [-Wunused-variable]
   10 |     const int CL = -10000, CR = 10000;
      |               ^~
nicelines.cpp:10:28: warning: unused variable 'CR' [-Wunused-variable]
   10 |     const int CL = -10000, CR = 10000;
      |                            ^~

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