Submission #592512

#	Time	Username	Problem	Language	Result	Execution time	Memory
592512		dantoh000	Nicelines (RMI20_nicelines)	C++14	82.25 / 100	71 ms	668 KiB

nicelines

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#include "nice_lines.h"

map<ll, map<ll, ld> > cache;

ld Q(ll x, ll y){
	if (cache[x].count(y)) return cache[x][y];
	else return cache[x][y] = query((ld)x, (ld)y);
}

ld getdiff(ll x, ll y){
	return Q(x, y+1) - Q(x, y);
}

vector<ll> ans;
ll X = 1000000;
void dnc(ll L, ll R, ld S, ld E){
	///printf("DNC %lld %lld %Lf %Lf\n",L,R,S,E);
	if (abs(S-E) < 1e-5){
		return;
	}
	if (L >= R) return;
	if (L+1 == R){
		ans.push_back(L+1);
		return;
	}
	ll mid = (L+R)/2;
	ld Q = getdiff(X, mid);
	dnc(L, mid, S, Q);
	dnc(mid, R, Q, E);
	
}

void solve(int subtask_id, int N) {
    ///printf("subtask_id = %d, N = %d\n", subtask_id, N);
    ll L = -100000000000;
    ll R = 100000000000;
    long double Q1 = getdiff(X, L);
    long double Q2 = getdiff(X, R);
    dnc(L, R, Q1, Q2);
    vector<int> a,b;
    for (auto x : ans){
		///printf("%lld\n",x);
		int A = round((ld)x/1000000);
		int B = x - A*1000000;
		a.push_back(A); b.push_back(B);
	}
    the_lines_are(a,b);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 13.2770368831 / 19
• Subtask 5: 20.7606272134 / 23
• Subtask 6: 17.213273598599997 / 27