oj.uz

Submission #829299

# Submission time Handle Problem Language Result Execution time Memory
829299 2023-08-18T08:29:51 Z rainboy Nicelines (RMI20_nicelines) C
0 / 100
 27 ms 208 KB 
#include "nice_lines_c.h"
#include <math.h>

#define N	100
#define M	10000
#define X	10000000
#define Y	((long long) M * X + M + 1)
#define eps	1e-9

typedef long double ld;

void solve(int subtask_id, int n) {
	static int aa[N], bb[N];
	int i, a, a_, b, lower, upper;
	long long y, y1, y2;
	ld u1, u2, v1, v1_, v2, v2_;

	a_ = -(M + 1), u1 = query(X, (long long) -(M + 1) * X + M), u2 = query(X, (long long) -M * X - M);
	for (i = 0; i < n; i++) {
		lower = a_, upper = M + 1, v1_ = -1, v2_ = -1;
		while (upper - lower > 1) {
			a = (lower + upper) / 2;
			v1 = query(X, (long long) a * X + M);
			v2 = query(X, (long long) (a + 1) * X - M);
			if (fabsl((v2 - v1) / (X - M * 2) - (u2 - u1) / (X - M * 2)) < eps)
				lower = a;
			else
				upper = a, v1_ = v1, v2_ = v2;
		}
		a = upper, v1 = v1_, v2 = v2_;
		y1 = (long long) (a_ + 1) * X - M, y2 = (long long) a * X + M;
		y = ((X - M * 2) * (v1 - u2) + y1 * (u2 - u1) - y2 * (v2 - v1)) / ((u2 - u1) - (v2 - v1));
		b = roundl(y - a * X);
		aa[i] = a, bb[i] = b;
		a_ = a, u1 = v1, u2 = v2;
	}
	the_lines_are(aa, bb);
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 13.0

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

Subtask #3
0.0 / 7.0

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

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -