Submission #1138619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138619		Math4Life2020	Nicelines (RMI20_nicelines)	C++20	0 / 100	50 ms	1440 KiB

nicelines

#include "nice_lines.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ld = long double;
using pii = pair<ll,ll>; using pld = pair<ld,ld>;
mt19937_64 gen;
vector<ll> ans;

ll XQ = 1e5; ld XQd = (ld)((ll)1e5);
ll AMAX = 1e4;
ld EPS = 1e-7;
ld TRD = (1.0L)/3;

bool eq(ld x, ld y) {
	return (abs(x-y)<=EPS);
}

bool eq(pld px, pld py) {
	return (eq(px.first,py.first)&&eq(px.second,py.second));
}

pld gline(pld px, pld py) { //get line segment
	return (pld){(py.second-px.second)/(py.first-px.first),(py.first*px.second-px.first*py.second)/(py.first-px.first)};
}

pld gseg(ll x) { //get segment corresponding to interval (x,x+1)
	return gline({TRD+x,query(XQd,TRD+x)},{2*TRD+x,query(XQd,2*TRD+x)});
}

ld gint(pld px, pld py) {
	return ((py.second-px.second)/(py.first-px.first));
}

void solvep(pld pl, pld pr) {
	if (eq(pl,pr)) {
		return;
	}
	ll xt = (ll)(EPS+gint(pl,pr));
	pld pm = gseg(xt);
	if (eq(pl,pm)||eq(pr,pm)) {
		ans.push_back(xt);
	} else {
		solvep(pl,pm);
		solvep(pm,pr);
	}
}

void solve(int subtask_id, int N) {
	ans.clear();
	gen = mt19937_64((long long) new char);
	solvep(gseg((ll)(-1e11)),gseg((ll)1e11));
	vector<int> va,vb;
	for (ll x0: ans) {
		if (x0>AMAX) {
			ll m0 = (x0+AMAX)/XQ;
			va.push_back(m0);
			ll b0 = x0-XQ*m0;
			vb.push_back(b0);
		} else if (x0<(-AMAX)) {
			ll m0 = -((AMAX-x0)/XQ);
			va.push_back(m0);
			ll b0 = x0-XQ*m0;
			vb.push_back(b0);
		} else {
			va.push_back(0);
			vb.push_back(x0);
		}
	}
	the_lines_are(va,vb);
}

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