oj.uz

답안 #406556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406556 2021-05-17T17:39:58 Z atoiz Nicelines (RMI20_nicelines) C++14
31 / 100
 7 ms 200 KB 
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
 
#include "nice_lines.h"
 
const int X = 100000;
 
bool equals(long double x, long double y) {
    // fprintf(stderr, "%.10lf %.10lf\n", double(x), double(y)); 
    return std::abs(x - y) < 0.000000001; 
}
 
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, slope_hi = dist_hi_0 - dist_hi_1;
    if (lo + 1 >= hi) return;
    if (equals(slope_lo, slope_hi)) return;
 
    fprintf(stderr, "%.10lf %.10lf\n", double(slope_lo), double(slope_hi));
    int64_t l = lo, r = hi;
    while (l < r) {
        int64_t m = (l + r + 1) >> 1;
        if ((slope_hi - slope_lo) * m > (dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) {
            r = m - 1;
        } else {
            l = m;
        }
    }
    int64_t md = l;
    fprintf(stderr, "%lld %lld %lld\n", lo, md, hi);
    // fprintf(stderr, "%lf\n", double(((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo)));
    // fprintf(stderr, "%lld\n", md);
 
    long double dist_md_0 = query(X, md);
    // fprintf(stderr, "%.10lf\n", double(dist_md_0));
    // fprintf(stderr, "%.10lf\n", double(dist_lo_0 + (md - lo) * slope_lo));
    // fprintf(stderr, "%.10lf\n", double(dist_hi_0 + (md - hi) * slope_hi));
 
    if (equals((dist_md_0 - dist_lo_0) / (md - lo), slope_lo) && equals((dist_md_0 - dist_hi_0) / (md - hi), slope_hi)) {
        md += (std::abs((slope_hi - slope_lo) * md - (dist_lo_0 - slope_lo * lo) + (dist_hi_0 - slope_hi * hi)) > std::abs((slope_hi - slope_lo) * (md + 1) - (dist_lo_0 - slope_lo * lo) + (dist_hi_0 - slope_hi * hi)));
        add(md, a, b);
        return;
    }
 
    long double dist_md_1 = query(X, md + 1);
 
    if (equals((dist_md_1 - dist_lo_0) / ((md + 1) - lo), slope_lo) && equals((dist_md_1 - dist_hi_0) / ((md + 1) - hi), slope_hi)) {
        add(md + 1, a, b);
        return;
    }
 
    solve_range(lo, dist_lo_0, dist_lo_1, md + 1, dist_md_1, dist_md_0, 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 = -1000020000ll, hi = 1000020000ll;
    std::vector<int> a, b;
    auto dist_lo_0 = query(X, lo);
    auto dist_lo_1 = dist_lo_0 + (dist_lo_0 - query(X, lo - 1000000)) / 1000000;
    auto dist_hi_0 = query(X, hi);
    auto dist_hi_1 = dist_hi_0 + (dist_hi_0 - query(X, hi + 1000000)) / 1000000;
    solve_range(lo, dist_lo_0, dist_lo_1, hi, dist_hi_0, dist_hi_1, a, b);
    the_lines_are(a, b);
}

Compilation message

nicelines.cpp: In function 'void solve_range(int64_t, long double, long double, int64_t, long double, long double, std::vector<int>&, std::vector<int>&)':
nicelines.cpp:43:25: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int64_t' {aka 'long int'} [-Wformat=]
   43 |     fprintf(stderr, "%lld %lld %lld\n", lo, md, hi);
      |                      ~~~^               ~~
      |                         |               |
      |                         long long int   int64_t {aka long int}
      |                      %ld
nicelines.cpp:43:30: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'int64_t' {aka 'long int'} [-Wformat=]
   43 |     fprintf(stderr, "%lld %lld %lld\n", lo, md, hi);
      |                           ~~~^              ~~
      |                              |              |
      |                              long long int  int64_t {aka long int}
      |                           %ld
nicelines.cpp:43:35: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'int64_t' {aka 'long int'} [-Wformat=]
   43 |     fprintf(stderr, "%lld %lld %lld\n", lo, md, hi);
      |                                ~~~^             ~~
      |                                   |             |
      |                                   long long int int64_t {aka long int}
      |                                %ld

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 200 KB Output is correct
2 Incorrect 7 ms 200 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# 결과 실행 시간 메모리 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 Incorrect 3 ms 200 KB Incorrect

Subtask #6
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 200 KB Output is correct
2 Incorrect 7 ms 200 KB Incorrect
3 Halted 0 ms 0 KB -