oj.uz

Submission #592573

# Submission time Handle Problem Language Result Execution time Memory
592573 2022-07-09T10:09:57 Z dantoh000 Nicelines (RMI20_nicelines) C++14
100 / 100
 12 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#include "nice_lines.h"

map<ll, map<ll, ld> > cache;

ld Q(ll x, ll y){
	if (cache[x].count(y)) return cache[x][y];
	else return cache[x][y] = query((ld)x, (ld)y);
}

ld getdiff(ll x, ll y){
	return Q(x, y+1) - Q(x, y);
}

vector<ll> ans;
vector<ld> diffs;
ll X = 20001;
void dnc(ll L, ll R, ld S, ld E){
	if (abs(S-E) < 1e-5){
		return;
	}
	///printf("DNC %lld %lld %.20Lf %.20Lf, %.20Lf\n",L,R,S,E, E-S);
	if (L >= R) return;
	for (auto x : diffs){
		if (abs(E-S-x) < 3e-11){
			///printf("FOUND %.20Lf %.20Lf = %.20Lf\n",S,E,E-S-x);
			long double difff = Q(X, R) - Q(X, L) - (R-L)*S;
			long double idx = difff/x;
			///printf("%Lf diffs\n", idx);
			ans.push_back(R-(int)round(idx));
			return;
		}
	}
	if (L+1 == R){
		ans.push_back(L+1);
		return;
	}
	ll mid = (L+R)/2;
	ld Q = getdiff(X, mid);
	dnc(L, mid, S, Q);
	dnc(mid, R, Q, E);
	
}

void solve(int subtask_id, int N) {
    ///printf("subtask_id = %d, N = %d\n", subtask_id, N);
    ll L = -10000*X - 10000 - 1;
    ll R = 10000*X + 10000 + 1;
    for (ll i = 0; i <= 10000; i++){
		long double D = (ld)(2.0)/sqrtl(i*i + 1);
		///printf("%.20Lf\n",D);
		diffs.push_back(D);
	}
    long double Q1 = getdiff(X, L);
    long double Q2 = getdiff(X, R);
    dnc(L, R, Q1, Q2);
    vector<int> a,b;
    for (auto x : ans){
		///printf("%lld\n",x);
		int A = round((ld)x/X);
		int B = x - A*X;
		a.push_back(A); b.push_back(B);
	}
    the_lines_are(a,b);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 600 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 592 KB Output is correct
2 Correct 9 ms 592 KB Output is correct
3 Correct 8 ms 592 KB Output is correct
4 Correct 9 ms 592 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 592 KB Output is correct
2 Correct 4 ms 592 KB Output is correct
3 Correct 5 ms 592 KB Output is correct
4 Correct 4 ms 592 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 592 KB Output is correct
2 Correct 9 ms 592 KB Output is correct
3 Correct 8 ms 592 KB Output is correct
4 Correct 9 ms 592 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 12 ms 592 KB Output is correct
10 Correct 9 ms 592 KB Output is correct
11 Correct 10 ms 592 KB Output is correct
12 Correct 9 ms 592 KB Output is correct