oj.uz

Submission #739538

# Submission time Handle Problem Language Result Execution time Memory
739538 2023-05-10T15:16:30 Z Kirill22 Nicelines (RMI20_nicelines) C++17
71.8724 / 100
 141 ms 936 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 (N >= 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 (N >= 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 1 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 #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 296 KB Output is correct
2 Correct 4 ms 428 KB Output is correct
3 Correct 3 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 324 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 5 ms 300 KB Output is correct
4 Correct 4 ms 208 KB Output is correct

Subtask #4
10.3850698066 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 96 ms 712 KB Output is partially correct
2 Partially correct 91 ms 880 KB Output is partially correct
3 Partially correct 95 ms 808 KB Output is partially correct
4 Partially correct 103 ms 712 KB Output is partially correct

Subtask #5
19.1402271309 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 37 ms 480 KB Output is partially correct
2 Partially correct 46 ms 480 KB Output is partially correct
3 Partially correct 39 ms 472 KB Output is partially correct
4 Partially correct 37 ms 468 KB Output is partially correct

Subtask #6
11.3471452395 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 96 ms 712 KB Output is partially correct
2 Partially correct 91 ms 880 KB Output is partially correct
3 Partially correct 95 ms 808 KB Output is partially correct
4 Partially correct 103 ms 712 KB Output is partially correct
5 Partially correct 37 ms 480 KB Output is partially correct
6 Partially correct 46 ms 480 KB Output is partially correct
7 Partially correct 39 ms 472 KB Output is partially correct
8 Partially correct 37 ms 468 KB Output is partially correct
9 Partially correct 119 ms 928 KB Output is partially correct
10 Partially correct 141 ms 828 KB Output is partially correct
11 Partially correct 129 ms 936 KB Output is partially correct
12 Partially correct 114 ms 920 KB Output is partially correct