oj.uz

Submission #739543

# Submission time Handle Problem Language Result Execution time Memory
739543 2023-05-10T15:23:13 Z Kirill22 Nicelines (RMI20_nicelines) C++17
74.6237 / 100
 155 ms 976 KB 
//#include "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 == 1) {
            if (abs(query(l) * 2 - query(l + 1) - query(l - 1)) > 1e-4) {
                res.push_back(l);
            }
            if (abs(query(r) * 2 - query(r + 1) - query(r - 1)) > 1e-4) {
                res.push_back(r);
            }
            return;
        }
        int m = (l + r) / 2;
        if (abs(query(m) * 2 - query(l) - query(r)) < 1e-4) {
            if (abs(query(l) * 2 - query(l + 1) - query(l - 1)) > 1e-4) {
                res.push_back(l);
            }
            if (abs(query(r) * 2 - query(r + 1) - query(r - 1)) > 1e-4) {
                res.push_back(r);
            }
            return;
        }
        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));
    }
    sort(res.begin(), res.end());
    res.resize(unique(res.begin(), res.end()) - res.begin());
    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 3 ms 312 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 3 ms 208 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
13.1509376945 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 652 KB Output is partially correct
2 Partially correct 58 ms 712 KB Output is partially correct
3 Partially correct 49 ms 544 KB Output is partially correct
4 Partially correct 63 ms 640 KB Output is partially correct

Subtask #5
19.1335173984 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 44 ms 596 KB Output is partially correct
2 Partially correct 38 ms 464 KB Output is partially correct
3 Partially correct 39 ms 452 KB Output is partially correct
4 Partially correct 39 ms 456 KB Output is partially correct

Subtask #6
11.339268597 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 87 ms 652 KB Output is partially correct
2 Partially correct 58 ms 712 KB Output is partially correct
3 Partially correct 49 ms 544 KB Output is partially correct
4 Partially correct 63 ms 640 KB Output is partially correct
5 Partially correct 44 ms 596 KB Output is partially correct
6 Partially correct 38 ms 464 KB Output is partially correct
7 Partially correct 39 ms 452 KB Output is partially correct
8 Partially correct 39 ms 456 KB Output is partially correct
9 Partially correct 155 ms 976 KB Output is partially correct
10 Partially correct 144 ms 892 KB Output is partially correct
11 Partially correct 113 ms 896 KB Output is partially correct
12 Partially correct 115 ms 924 KB Output is partially correct