Submission #592488

#	Time	Username	Problem	Language	Result	Execution time	Memory
592488		errorgorn	Nicelines (RMI20_nicelines)	C++17	0 / 100	55 ms	1352 KiB

nicelines

#include "nice_lines.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

#define double long double

const double EPS=1e-8;
const double Y=69.420177013;

#define di pair<double,int>
vector<di> v;

double grad(double X){
	return (query(X+EPS,Y)-query(X,Y))/EPS;
}

double grad2(double X){
	return (query(X,Y+EPS)-query(X,Y))/EPS;
}

vector<signed> ansA,ansB;

void rec(double l,double r,double gl,double gr){
	if (r-l<1e-5){
		double g=grad2(r)-grad2(l);
		//cout<<l<<" "<<r<<" "<<g<<endl;
		
		double best=1e9;
		int idx=-1e9;
		for (auto [a,b]:v){
			if (fabsl(a-g)<best){
				best=fabsl(a-g);
				idx=b;
			}
		}
		
		ansA.pub(idx);
		ansB.pub(roundl(Y+l*idx));
	}
	else{
		double m=(l+r)/2;
		double g=grad(m);
		if (fabsl(gl-g)>1e-2) rec(l,m,gl,g);
		if (fabsl(gr-g)>1e-2) rec(m,r,g,gr);
	}
}

void solve(signed subtask_id, signed N) {
	cout<<fixed<<setprecision(12);
	
	for (int x=1;x<=10000;x++){
		v.pub({2.0/sqrtl(1+x*x),x});
		v.pub({-2.0/sqrtl(1+x*x),-x});
	}
	
    rec(-10100,10100,grad(-10100),grad(10100));
    
    the_lines_are(ansA,ansB);
}

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