Submission #592555

#	Time	Username	Problem	Language	Result	Execution time	Memory
592555		errorgorn	Nicelines (RMI20_nicelines)	C++17	97.20 / 100	27 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
 
struct line{
	double a,b; //ensure that a^2+b^2=1, i.e. norm vec
	double r;
	
	line(double A,double B){
		double g=sqrtl(A*A+1);
		a=-A/g,b=1.0/g;
		r=B/g;
	}
	
	double dist(double x,double y){
		return fabsl(a*x+b*y-r);
	}
};
vector<line> ans;
 
const double Y=0.420177013;
 
vector<pair<double,int>> v;
map<pair<double,double>,double> memo;

double Query(double X,double Y){
	if (!memo.count({X,Y})) memo[{X,Y}]=query(X,Y);
	return memo[{X,Y}];
}

double grad(double X){
	return (Query(X+1e-10,Y)-Query(X,Y))/1e-10;
}

double grad2(double X){
	return (Query(X,Y+1e-7)-Query(X,Y))/1e-7;
}

vector<signed> ansA,ansB;

void rec(double l,double r,double gl,double gr){
	if (gr-gl<2.1 && r-l<100){
		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);
		
		double L=l,R=r;
		double ql=Query(L,Y);
		double qr=Query(R,Y);
		while (abs(idx)*(r-l)>0.4){
			double m=(r+l)/2,qm=query(m,Y);
			
			if (fabsl((qm-ql)/(m-L)-gl)<fabsl((qr-qm)/(R-m)-gr)) l=m;
			else r=m;
		}
		
		ansB.pub(roundl(Y-l*idx));
		ans.pub({ansA.back(),ansB.back()});
	}
	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));
	
	if (sz(ansA)!=N){
		double y=query(0,-10000);
		for (auto it:ans) y-=it.dist(0,-10000);
		ansA.pub(0);
		ansB.pub(roundl(y-10000));
	}
	
	the_lines_are(ansA,ansB);
}

Compilation message (stderr)

nicelines.cpp: In function 'void rec(long double, long double, long double, long double)':
nicelines.cpp:90:21: warning: narrowing conversion of 'ansA.std::vector<int>::back()' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   90 |   ans.pub({ansA.back(),ansB.back()});
      |            ~~~~~~~~~^~
nicelines.cpp:90:33: warning: narrowing conversion of 'ansB.std::vector<int>::back()' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   90 |   ans.pub({ansA.back(),ansB.back()});
      |                        ~~~~~~~~~^~

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