oj.uz

Submission #406455

# Submission time Handle Problem Language Result Execution time Memory
406455 2021-05-17T15:37:42 Z atoiz Nicelines (RMI20_nicelines) C++14
88.9228 / 100
 212 ms 1300 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) { 
	return std::abs(x - y) <= std::max((long double) 0.00000001, 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)));
	long double dist_y = query(X, y - 20000);
	fprintf(stderr, "%lf == %lf\n", double(dist_y), double(dist_lo_0 + (y - lo) * slope_lo));
	fprintf(stderr, "%lf == %lf\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;
	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
0.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 Incorrect 212 ms 1300 KB Incorrect
4 Halted 0 ms 0 KB -

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 200 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 1 ms 200 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #4
18.9681287768 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 308 KB Output is partially correct
2 Partially correct 10 ms 300 KB Output is partially correct
3 Partially correct 12 ms 308 KB Output is partially correct
4 Partially correct 12 ms 308 KB Output is partially correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 200 KB Output is correct
2 Correct 4 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
26.9547093144 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 308 KB Output is partially correct
2 Partially correct 10 ms 300 KB Output is partially correct
3 Partially correct 12 ms 308 KB Output is partially correct
4 Partially correct 12 ms 308 KB Output is partially correct
5 Correct 4 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 4 ms 200 KB Output is correct
8 Correct 3 ms 200 KB Output is correct
9 Correct 10 ms 300 KB Output is correct
10 Correct 13 ms 304 KB Output is correct
11 Partially correct 10 ms 312 KB Output is partially correct
12 Correct 10 ms 456 KB Output is correct