Submission #743204

#	Time	Username	Problem	Language	Result	Execution time	Memory
743204		jamezzz	Nicelines (RMI20_nicelines)	C++17	78.40 / 100	136 ms	560 KiB

nicelines

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

#define pf printf
#define pb push_back
#define maxn 10000
#define EPS 1e-5
#define dist(a,b,x,y) (ld)abs(y-a*x-b)/pow(1+a*a,0.5)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

map<ii,ld> memo;
vector<ii> know;

ld ask(ld x,ld y){
	ld res;
	if(x==0){
		if(memo.find({(int)x,(int)y})!=memo.end())res=memo[{(int)x,(int)y}];
		else res=memo[{(int)x,(int)y}]=query(x,y);
	}
	else res=query(x,y);
	for(auto[a,b]:know)res-=dist(a,b,x,y);
	return res;
}

void solve(int subtask_id,int N){
	for(int i=0;i<N;++i){
		int lo=-10000,hi=10000;
		if(subtask_id==4)lo=-500,hi=500;
		while(hi-lo>=3){
			int mid1=lo+((hi-lo)/3),mid2=lo+((hi-lo)*2/3);
			if(ask(0,mid1)>ask(0,mid2))lo=mid1;
			else hi=mid2;
		}
		ld best=1e18;int res=lo;
		for(int i=lo;i<=hi;++i){
			ld tmp=ask(0,i);
			if(tmp<best)best=tmp,res=i;
		}
		int b=(int)res;
		lo=-10000,hi=10000;
		if(subtask_id==4)lo=-500,hi=500;
		while(hi-lo>=3){
			int mid1=lo+((hi-lo)/3),mid2=lo+((hi-lo)*2/3);
			if(ask(EPS,mid1*EPS+b)>ask(EPS,mid2*EPS+b))lo=mid1;
			else hi=mid2;
		}
		best=1e18;res=lo;
		for(int i=lo;i<=hi;++i){
			ld tmp=ask(EPS,i*EPS+b);
			if(tmp<best)best=tmp,res=i;
		}
		int a=(int)res;
		know.push_back({a,b});
	}
	vector<int> A,B;
	for(auto[a,b]:know)A.pb(a),B.pb(b);
	the_lines_are(A,B);
}

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