oj.uz

Submission #406367

# Submission time Handle Problem Language Result Execution time Memory
406367 2021-05-17T13:28:20 Z atoiz Nicelines (RMI20_nicelines) C++14
0 / 100
 177 ms 1280 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) < 1e-10; }
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);
}

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 (dist_lo_0 + slope_lo * (hi - lo) == dist_hi_0) return;
	if (dist_hi_0 + slope_hi * (lo - hi) == dist_lo_0) return;

	int64_t md = int64_t(((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo));
	// fprintf(stderr, "%lf\n", (slope_hi - slope_lo));
	long double dist_md_0 = query(X, md);

	if (equals(dist_md_0, dist_lo_0 + (md - lo) * slope_lo) && equals(dist_md_0, dist_hi_0 + (md - hi) * slope_hi)) {
		add(md, a, b);
		solve_range(lo, dist_lo_0, dist_lo_1, md, dist_md_0, query(X, md - 1), a, b);
		solve_range(md, dist_md_0, query(X, md + 1), hi, dist_hi_0, dist_hi_1, 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);
		solve_range(lo, dist_lo_0, dist_lo_1, md + 1, dist_md_1, dist_md_0, a, b);
		solve_range(md + 1, dist_md_1, query(X, md + 2), hi, dist_hi_0, dist_hi_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 = -10000000000ll, hi = 10000000000ll;
	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);
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 1188 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Wrong query
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Wrong query
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 1280 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Wrong query
2 Halted 0 ms 0 KB -