Submission #402079

#	Time	Username	Problem	Language	Result	Execution time	Memory
402079		maximath_1	Nicelines (RMI20_nicelines)	C++11	92.99 / 100	74 ms	564 KiB

nicelines

#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;

#define ll long long
#define ld long double
ll lim = 10000;
const ld eps = 1e-6;
map<pair<ll, ll>, ld> mp;
vector<int> a, b;

ld que(ll x, ll y){
	if(mp.count({x, y})) return mp[{x, y}];
	return mp[{x, y}] = query(x, y);
}

ll dv(ll a, ll b){
	if(a < 0) return (a - b + 1) / b;
	return a / b;
}

void solve(int subtask_id, int N){
	mp.clear();
	if(subtask_id == 4) lim = 500;

	ll x = lim * 2 + 1, y = x * lim + lim;
	ld diff = que(x, -y + 1) - que(x, -y);
	ll last = -y;

	for(int i = 0; i < N; i ++){
		ll lf = 1, rg = lim;
		while(fabs(que(x, last + rg) - (que(x, last) + rg * diff)) < eps){
			diff = (que(x, last + rg) - que(x, last)) / rg;
			rg *= 8;
		}

		for(ll md; lf < rg;){
			md = (lf + rg) / 2;
			if(fabs(que(x, last + md) - (que(x, last) + md * diff)) < eps) lf = md + 1;
			else rg = md;
		}

		last += lf - 1;
		a.push_back((int)dv(last + lim, x));
		b.push_back((int)(last - a.back() * x));

		diff = que(x, last + 1) - que(x, last);
	}

	the_lines_are(a, b);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 17.258168369 / 19
• Subtask 5: 22.204896854 / 23
• Subtask 6: 22.530006252 / 27