oj.uz

Submission #739539

# Submission time Handle Problem Language Result Execution time Memory
739539 2023-05-10T15:17:24 Z Kirill22 Nicelines (RMI20_nicelines) C++17
74.6439 / 100
 124 ms 908 KB 
//#include "nice_lines.h"
#include "bits/stdc++.h"

using namespace std;

long double query(long double x, long double y);
void the_lines_are(std::vector<int> a, std::vector<int> b);

int x = (1 << 15);

map<int, long double> mem;

long double query(int y) {
    if (mem.find(y) != mem.end()) {
        return mem[y];
    }
    return mem[y] = query(x, y);
}

void solve(int subtask_id, int N) {
    if (subtask_id == 4) {
        x = 1024;
    }
    vector<int> res;
    function<void(int, int)> solve = [&] (int l, int r) {
        //cout << l << " " << r << endl;
        if (r - l < 2) {
            return;
        }
        int m = (l + r) / 2;
        if (abs(query(m) * 2 - query(l) - query(r)) < 1e-4) {
            return;
        }
        if (abs(query(m) * 2 - query(m + 1) - query(m - 1)) > 1e-4) {
            res.push_back(m);
        }
        solve(l, m);
        solve(m, r);
    };
    if (subtask_id == 4) {
        solve(-x * (1 << 14), x * (1 << 14));
    } else {
        solve(-x * (1 << 14), x * (1 << 14));
    }
    vector<int> a, b;
    for (int i = 0; i < N; i++) {
        int y = res[i] % x;
        if (y < 0) {
            y += x;
        }
        if (y >= x / 2) {
            y -= x;
        }
        b.push_back(y);
        a.push_back((res[i] - y) / x);
    }
    the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 3 ms 320 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 5 ms 316 KB Output is correct

Subtask #4
13.156480517 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 59 ms 756 KB Output is partially correct
2 Partially correct 65 ms 608 KB Output is partially correct
3 Partially correct 60 ms 612 KB Output is partially correct
4 Partially correct 60 ms 648 KB Output is partially correct

Subtask #5
19.1402271309 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 28 ms 444 KB Output is partially correct
2 Partially correct 37 ms 472 KB Output is partially correct
3 Partially correct 36 ms 504 KB Output is partially correct
4 Partially correct 40 ms 596 KB Output is partially correct

Subtask #6
11.3471452395 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 59 ms 756 KB Output is partially correct
2 Partially correct 65 ms 608 KB Output is partially correct
3 Partially correct 60 ms 612 KB Output is partially correct
4 Partially correct 60 ms 648 KB Output is partially correct
5 Partially correct 28 ms 444 KB Output is partially correct
6 Partially correct 37 ms 472 KB Output is partially correct
7 Partially correct 36 ms 504 KB Output is partially correct
8 Partially correct 40 ms 596 KB Output is partially correct
9 Partially correct 120 ms 876 KB Output is partially correct
10 Partially correct 122 ms 900 KB Output is partially correct
11 Partially correct 117 ms 896 KB Output is partially correct
12 Partially correct 124 ms 908 KB Output is partially correct