제출 #402071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402071		maximath_1	Nicelines (RMI20_nicelines)	C++11	0 / 100	38 ms	340 KiB

nicelines

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

#define ll long long
#define ld long double
const ll lim = 20000;
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){
	return a / b + ((a ^ b) < 0 && a % b);
}

void solve(int subtask_id, int N){
	mp.clear();

	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;
		}

		ll rs = rg;
		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 rs = md, rg = md - 1;
		}

		last += rs;
		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: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27