Submission #398549

#	Time	Username	Problem	Language	Result	Execution time	Memory
398549		model_code	Nicelines (RMI20_nicelines)	C++17	90.36 / 100	76 ms	748 KiB

nicelines

/**
* user:  lendvaj-c30
* fname: Dorijan
* lname: Lendvaj
* task:  NiceLines
* score: 90.35555
* date:  2020-12-04 11:41:12.308338
*/
#include "nice_lines.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
using ld=long double;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
using namespace std;

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

map<pll,bool> bio;
map<pll,ld> res;

ld quer(ll a,ll b)
{
	if (bio[{a,b}]) return res[{a,b}];
	bio[{a,b}]=1;
	return res[{a,b}]=query(a,b);
}

ll di(ll a,ll b)
{
	if (a<0) return (a-b+1)/b;
	else return a/b;
}

void solve(int subtask_id, int N) {
	bio.clear();
	res.clear();
	ll lim=10000;
	if (subtask_id==4) lim=500;
    ll x=lim*2+1,y=(x+2)*lim;
    ld d1=quer(x,-y),d2=quer(x,-y+1);
    ld po=d2-d1;
    ll la=-y;
    vi a,b;
    cout<<fixed<<setprecision(6);
    for (int i=0;i<N;++i)
    {
		ll pom=200;
		while (abs(quer(x,la+pom)-(quer(x,la)+po*pom))<1e-5)
		{
			//cout<<x<<' '<<la<<' '<<la+pom<<' '<<quer(x,la)<<' '<<quer(x,la+pom)<<' '<<po<<endl;
			//cout<<pom<<' '<<query(x,la)+po*pom<<' '<<query(x,la+pom)<<endl;
			po=(quer(x,la+pom)-quer(x,la))/pom;
			pom*=2;
		}
		ll lo=pom/2+1,hi=pom;
		while (lo<hi)
		{
			ll mid=(lo+hi)/2;
			if (abs(quer(x,la+mid)-(quer(x,la)+po*mid))<1e-5) lo=mid+1;
			else hi=mid;
		}
		la=la+lo-1;
		a.pb(di(la+lim,x));
		b.pb(la-a.back()*x);
		d1=quer(x,la);
		d2=quer(x,la+1);
		po=d2-d1;
	}
    the_lines_are(a, b);
}

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