oj.uz

답안 #739567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739567 2023-05-10T16:15:29 Z Kirill22 Nicelines (RMI20_nicelines) C++17
100 / 100
 8 ms 456 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);
}

pair<long double, long double> line(int a, int b) {
    long double A = query(a);
    long double B = query(b);
    long double k = (B - A) / (b - a);
    return {k, A - k * a};
}

long double intersection(pair<long double, long double> a, pair<long double, long double> b) {
    return (a.second - b.second) / (b.first - a.first);
}

bool check(int a, int b, int c) {
    auto L = line(a, b);
    auto R = line(b, c);
    if (abs(L.first - R.first) < 1e-9) {
        return true;
    }
    return false;
}

void solve(int subtask_id, int N) {
    vector<int> res;
    function<void(int, int, int, int)> solve = [&] (int l, int l1, int r, int r1) {
        auto L = line(l, l1);
        auto R = line(r, r1);
        if (abs(L.first - R.first) < 1e-9) {
            return;
        }
        int X = round(intersection(L, R));
        if (check(l, l1, X) && check(X, r, r1)) {
            res.push_back(X);
            return;
        }
        solve(l, l1, X - 1, X);
        solve(X - 1, X, r, r1);
    };
    solve(-x * (1 << 14), -x * (1 << 14) + 3 * x, x * (1 << 14) - 3 * x, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 300 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 324 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 3 ms 316 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 324 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 3 ms 316 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Correct 2 ms 316 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 2 ms 208 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 7 ms 456 KB Output is correct
11 Correct 6 ms 332 KB Output is correct
12 Correct 5 ms 336 KB Output is correct