Submission #829306

#	Time	Username	Problem	Language	Result	Execution time	Memory
829306		rainboy	Nicelines (RMI20_nicelines)	C11	0 / 100	29 ms	208 KiB

nicelines

#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 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27