oj.uz

Submission #743256

# Submission time Handle Problem Language Result Execution time Memory
743256 2023-05-17T09:16:10 Z jamezzz Nicelines (RMI20_nicelines) C++17
0 / 100
 47 ms 440 KB 
#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-1;++i){
		int lo=-10000,hi=10000,mid,res;
		if(subtask_id==4)lo=-500,hi=500;
		while(lo<=hi){
			mid=lo+((hi-lo)>>1);
			if(ask(0,mid)>ask(0,mid+1))lo=mid+1;
			else res=mid,hi=mid-1;
		}
		int b=(int)res;
		lo=-10000,hi=10000;
		if(subtask_id==4)lo=-500,hi=500;
		while(lo<=hi){
			mid=lo+((hi-lo)>>1);
			if(ask(EPS,mid*EPS+b)>ask(EPS,(mid+1)*EPS+b))lo=mid+1;
			else res=mid,hi=mid-1;
		}
		int a=(int)res;
		know.push_back({a,b});
	}
	
	ld x1=ask(0,10000),x2=ask(0,10001);
	ld inv=1/(x2-x1);
	int a=(int)(pow(inv*inv-1,0.5)+1e-3);
	//printf("%.20Lf\n",10001-x2*pow(a*a+1,0.5));
	int b=(int)(10001-x2*pow(a*a+1,0.5)+1e-16);
	//printf("%.20Lf %.20Lf\n",dist(a,b,1,10001),ask(1,10001));
	if(abs(dist(a,b,1,10001)-ask(1,10001))>1e-3)a=-a;
	know.pb({a,b});
	
	//printf("last %d %d\n",a,b);
	
	vector<int> A,B;
	for(auto[a,b]:know)A.pb(a),B.pb(b);
	the_lines_are(A,B);
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

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

Subtask #3
0.0 / 7.0

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

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 33 ms 328 KB Output is partially correct
2 Incorrect 47 ms 328 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 440 KB Output is partially correct
2 Incorrect 19 ms 328 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 33 ms 328 KB Output is partially correct
2 Incorrect 47 ms 328 KB Incorrect
3 Halted 0 ms 0 KB -