oj.uz

Submission #739536

# Submission time Handle Problem Language Result Execution time Memory
739536 2023-05-10T15:14:33 Z Kirill22 Nicelines (RMI20_nicelines) C++17
13.1565 / 100
 76 ms 672 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 << 16);

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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
13.156480517 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 64 ms 668 KB Output is partially correct
2 Partially correct 76 ms 648 KB Output is partially correct
3 Partially correct 58 ms 672 KB Output is partially correct
4 Partially correct 58 ms 584 KB Output is partially correct

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 384 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 64 ms 668 KB Output is partially correct
2 Partially correct 76 ms 648 KB Output is partially correct
3 Partially correct 58 ms 672 KB Output is partially correct
4 Partially correct 58 ms 584 KB Output is partially correct
5 Incorrect 25 ms 384 KB Incorrect
6 Halted 0 ms 0 KB -