Submission #592610

#	Time	Username	Problem	Language	Result	Execution time	Memory
592610		tqbfjotld	Nicelines (RMI20_nicelines)	C++14	96.89 / 100	24 ms	500 KiB

nicelines

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

map<pair<long double,long double>,long double> querymem;

long double mquery(long double x, long double y){
	if (querymem.count({x,y})) return querymem[{x,y}];
	return querymem[{x,y}] = query(x,y);
}

map<int,long double> memot;

long double checkthing(int a, bool side){
	//printf("call c %d\n",a);
	if (memot.count(a)) return memot[a];
	if (true){
		long double t1 = 100000;
		long double res1 = mquery(t1,t1*a+10001);
		long double res2 = mquery(t1,t1*a+10000);
		return memot[a] = res2-res1;
	}
	else{
		long double t1 = 100000;
		long double res1 = mquery(t1,t1*a-10001);
		long double res2 = mquery(t1,t1*a-10000);
		return memot[a] = res2-res1;
	}
}

const long double EPS = 0.000000001l;
vector<pair<int,int> > lines;

//(a,b]
int solvet(int a, int b){
	if (a==b)return 0;
	long double res1 = checkthing(a,true);
	long double res2 = checkthing(b,true);
	//printf("%Lf %Lf myres\n",res1,res2);
	if (fabsl(res1-res2)<EPS) return 0;
	if (a+1==b){
		long double t1 = 100000;
		long double res1 = mquery(t1,t1*b+10001);
		long double res2 = mquery(t1,t1*b+10000);
		long double res3 = mquery(t1,t1*b-90000);
		long double expectedres3 = res2+(res2-res1)*100000;
		long double thing = (res3-expectedres3)/2*sqrtl(b*b+1);
		//printf("%Lf thing = %d\n",thing,-10000+(int)roundl(thing));
		lines.push_back({b,-90000+(int)roundl(thing)});
		return 1;
	}
	int mid = (a+b)/2;
	return solvet(a,mid)+solvet(mid,b);
}

//(a,b]
int solvet2(int a, int b){
	if (a==b) return 0;
	long double res1 = checkthing(a,false);
	long double res2 = checkthing(b,false);
	//printf("%Lf %Lf myres\n",res1,res2);
	if (fabsl(res1-res2)<EPS) return 0;
	if (a+1==b){
		long double t1 = 100000;
		long double res1 = mquery(t1,t1*b+10001);
		long double res2 = mquery(t1,t1*b+10000);
		long double res3 = mquery(t1,t1*b-90000);
		long double expectedres3 = res2+(res2-res1)*100000;
		long double thing = (res3-expectedres3)/2*sqrtl(b*b+1);
		//printf("%Lf thing = %d\n",thing,-10000+(int)roundl(thing));
		lines.push_back({b,-90000+(int)roundl(thing)});
		return 1;
	}
	int mid = (a+b)/2;
	return solvet2(a,mid)+solvet2(mid,b);
}


void solve(int subtask_id, int N) {
	int t1;
	if (subtask_id==4){
		t1 = solvet(-1,500)+solvet2(-500,-1);
	}
	else{
		t1 = solvet(-1,10000)+solvet2(-10001,-1);
	}
	
    vector<int> ansa;
    vector<int> ansb;
    assert(t1==N);
    for (auto x : lines){
		ansa.push_back(x.first);
		ansb.push_back(x.second);
	}
    the_lines_are(ansa,ansb);
}

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