oj.uz

Submission #942855

# Submission time Handle Problem Language Result Execution time Memory
942855 2024-03-11T05:25:10 Z Pannda Nicelines (RMI20_nicelines) C++17
45.0508 / 100
 48 ms 1516 KB 
#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(10, 20);
        long long last = -5.1e7;
        for (int i = 0; i < n; i++) {
            long long l = last + 1, r = 5.1e7;
            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

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

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

Subtask #2
13.0 / 13.0

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

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 696 KB Output is correct
2 Incorrect 2 ms 456 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 1380 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
21.0508230871 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 1516 KB Output is partially correct
2 Partially correct 16 ms 1488 KB Output is partially correct
3 Partially correct 12 ms 692 KB Output is partially correct
4 Partially correct 12 ms 1208 KB Output is partially correct

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 1380 KB Incorrect
2 Halted 0 ms 0 KB -