oj.uz

Submission #592426

# Submission time Handle Problem Language Result Execution time Memory
592426 2022-07-09T07:44:23 Z tqbfjotld Nicelines (RMI20_nicelines) C++14
0 / 100
 12 ms 376 KB 
#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 = 1e-5;
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-10000);
		long double expectedres3 = res2+(res2-res1)*20000;
		long double thing = (res3-expectedres3)/2*sqrtl(b*b+1);
		//printf("%Lf thing = %d\n",thing,-10000+(int)roundl(thing));
		lines.push_back({b,10000-(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-10000);
		long double expectedres3 = res2+(res2-res1)*20000;
		long double thing = (res3-expectedres3)/2*sqrtl(b*b+1);
		//printf("%Lf thing = %d\n",thing,-10000+(int)roundl(thing));
		lines.push_back({b,10000-(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 = 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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 376 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 376 KB Incorrect
2 Halted 0 ms 0 KB -