#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) { return std::abs(x - y) < 0.00001; }
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;
int64_t md = roundDouble(((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo));
fprintf(stderr, "%lld %lld\n", lo, hi);
fprintf(stderr, "%.10lf %.10lf\n", double(slope_lo), double(slope_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)) {
fprintf(stderr, "%s\n", "N");
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;
}
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;
solve_range(lo, query(X, lo), query(X, lo + 1), hi, query(X, hi), query(X, 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:30:22: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int64_t' {aka 'long int'} [-Wformat=]
30 | fprintf(stderr, "%lld %lld\n", lo, hi);
| ~~~^ ~~
| | |
| | int64_t {aka long int}
| long long int
| %ld
nicelines.cpp:30:27: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'int64_t' {aka 'long int'} [-Wformat=]
30 | fprintf(stderr, "%lld %lld\n", lo, hi);
| ~~~^ ~~
| | |
| | int64_t {aka long int}
| long long int
| %ld
nicelines.cpp:33:25: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int64_t' {aka 'long int'} [-Wformat=]
33 | fprintf(stderr, "%lld\n", md);
| ~~~^ ~~
| | |
| | int64_t {aka long int}
| long long int
| %ld
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
