Submission #592514

#	Time	Username	Problem	Language	Result	Execution time	Memory
592514		dantoh000	Nicelines (RMI20_nicelines)	C++14	86.71 / 100	63 ms	712 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 = 20001;
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 = -10000*X - 10000 - 1;
    ll R = 10000*X + 10000 + 1;
    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/X);
		int B = x - A*X;
		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: 14.8622838084 / 19
• Subtask 5: 21.3779224838 / 23
• Subtask 6: 19.469931236100003 / 27