oj.uz

Submission #406392

# Submission time Handle Problem Language Result Execution time Memory
406392 2021-05-17T14:14:57 Z atoiz Nicelines (RMI20_nicelines) C++14
23 / 100
 176 ms 1128 KB 
    #include <stdio.h>
    #include <math.h>
    #include <algorithm>
    #include <vector>
     
    #include "nice_lines.h"
     
    const int X = 100000;
     
    bool zero(long double x) { return std::abs(x) < 1; }
    bool equals(long double x, long double y) { return zero(x - y); }
     
    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 diff_lo = (dist_lo_1 - dist_lo_0), diff_hi = (dist_hi_1 - dist_hi_0);
     
    	int64_t y = roundDouble(((dist_lo_0 * 40000 - diff_lo * lo) - (dist_hi_0 * 40000 - diff_hi * hi)) / (diff_hi - diff_lo));
     
    	// fprintf(stderr, "%lf\n", double(((dist_lo_0 * 40000 - diff_lo * lo) - (dist_hi_0 * 40000 - diff_hi * hi)) / (diff_hi - diff_lo)));
    	long double dist_y = query(X, y - 20000);
    	// fprintf(stderr, "%lf == %lf\n", double(dist_y * 40000), double(dist_lo_0 * 40000 + (y - lo) * diff_lo));
    	// fprintf(stderr, "%lf == %lf\n", double(dist_y * 40000), double(dist_hi_0 * 40000 + (y - hi) * diff_hi));
    	if (equals(dist_y * 40000, dist_lo_0 * 40000 + (y - lo) * diff_lo) && equals(dist_y * 40000, dist_hi_0 * 40000 + (y - hi) * diff_hi)) {
    		add(y - 20000, a, b);
    		return;
    	}
     
    	int64_t md = y - (y % 100000) + 50000 + (y % 100000 > 80000) * 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 = -10000000000ll + 50000, hi = 10000000000ll + 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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 200 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 1100 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 1104 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 1128 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

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

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 1128 KB Incorrect
2 Halted 0 ms 0 KB -