Submission #829310

#	Time	Username	Problem	Language	Result	Execution time	Memory
829310		rainboy	Nicelines (RMI20_nicelines)	C++17	91.68 / 100	35 ms	284 KiB

nicelines

#include "nice_lines.h"
#include <cmath>
#include <vector>

using namespace std;

typedef long double ld;
typedef vector<int> vi;

const int N = 100;
const int M = 10000;
const int X = 10000000;
const ld eps = 1e-9;

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

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 15.8378203784 / 19
• Subtask 5: 22.3323817462 / 23
• Subtask 6: 22.506376327199998 / 27