oj.uz

Submission #406568

# Submission time Handle Problem Language Result Execution time Memory
406568 2021-05-17T18:00:23 Z atoiz Nicelines (RMI20_nicelines) C++14
100 / 100
 12 ms 428 KB 
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <assert.h>
#include <vector>

#include "nice_lines.h"

const int X = 100000;

bool equals(long double x, long double y) { 
    return std::abs(x - y) <= std::max((long double) 0.0000001, std::abs(std::max(x, y) / 10000000000)); 
}

void add(int64_t Y, std::vector<int> &A, std::vector<int> &B) {
    int b = int(Y % X);
    while (b > 10000) b -= X;
    while (b < -10000) b += X;
    A.push_back((Y - b) / X), B.push_back(b);
}

int64_t roundDouble(long double x) {
    if (x < 0) return -int64_t(0.5 - x);
    else return int64_t(x + 0.5);
}

void solve_range(int64_t lo, long double dist_lo_0, long double dist_lo_1, int64_t hi, long double dist_hi_0, long double dist_hi_1, std::vector<int> &a, std::vector<int> &b) {
    long double slope_lo = (dist_lo_1 - dist_lo_0) / 40000, slope_hi = (dist_hi_1 - dist_hi_0) / 40000;
    if (equals(slope_lo, slope_hi)) return;
    if (lo >= hi) return;
    // fprintf(stderr, "%lld %lld\n", lo, hi);
    // fprintf(stderr, "%lf %lf\n", (double) slope_lo, (double) slope_hi);

    long double dy = ((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo);
    // fprintf(stderr, "%lf\n", (double) dy);
    int64_t y = roundDouble(dy);
    // fprintf(stderr, "%lf\n", double(((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo)));
    if (std::abs(dy - y) < 0.3) {
        long double dist_y = query(X, y - 20000);
        fprintf(stderr, "%.10lf == %.10lf\n", double(dist_y), double(dist_lo_0 + (y - lo) * slope_lo));
        fprintf(stderr, "%.10lf == %.10lf\n", double(dist_y), double(dist_hi_0 + (y - hi) * slope_hi));
        if (equals(dist_y, dist_lo_0 + (y - lo) * slope_lo) && equals(dist_y, dist_hi_0 + (y - hi) * slope_hi)) {
            add(y - 20000, a, b);
            return;
        }
    }

    int64_t md = y - (y % 100000) + 50000 + (y % 100000 > 80000) * 100000;
    // assert(md != lo && md != hi);
    if (md == lo) md += 100000;
    if (md == hi) md -= 100000;
    long double dist_md_0 = query(X, md - 20000);
    long double dist_md_1 = query(X, md + 20000);

    solve_range(lo, dist_lo_0, dist_lo_1, md, dist_md_0, dist_md_1, a, b);
    solve_range(md, dist_md_0, dist_md_1, hi, dist_hi_0, dist_hi_1, a, b);
}

void solve(int subtask_id, int N) {
    int64_t lo = -1100000000ll + 50000, hi = 1100000000ll + 50000;
    std::vector<int> a, b;
    solve_range(lo, query(X, lo - 20000), query(X, lo + 20000), hi, query(X, hi - 20000), query(X, hi + 20000), a, b);
    the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 276 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 316 KB Output is correct
2 Correct 11 ms 288 KB Output is correct
3 Correct 12 ms 428 KB Output is correct
4 Correct 11 ms 308 KB Output is correct

Subtask #5
23.0 / 23.0

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

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 316 KB Output is correct
2 Correct 11 ms 288 KB Output is correct
3 Correct 12 ms 428 KB Output is correct
4 Correct 11 ms 308 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 3 ms 200 KB Output is correct
8 Correct 4 ms 200 KB Output is correct
9 Correct 7 ms 312 KB Output is correct
10 Correct 8 ms 200 KB Output is correct
11 Correct 9 ms 200 KB Output is correct
12 Correct 9 ms 308 KB Output is correct