oj.uz

Submission #592568

# Submission time Handle Problem Language Result Execution time Memory
592568 2022-07-09T10:06:52 Z dantoh000 Nicelines (RMI20_nicelines) C++14
92.2344 / 100
 140 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) < 1e-13){
			///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 1 ms 592 KB Output is correct
2 Correct 2 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 600 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct

Subtask #3
7.0 / 7.0

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

Subtask #4
16.2341321102 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 68 ms 592 KB Output is partially correct
2 Partially correct 68 ms 592 KB Output is partially correct
3 Partially correct 60 ms 592 KB Output is partially correct
4 Partially correct 72 ms 596 KB Output is partially correct

Subtask #5
23.0 / 23.0

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

Subtask #6
22.0003021458 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 68 ms 592 KB Output is partially correct
2 Partially correct 68 ms 592 KB Output is partially correct
3 Partially correct 60 ms 592 KB Output is partially correct
4 Partially correct 72 ms 596 KB Output is partially correct
5 Correct 6 ms 592 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 8 ms 592 KB Output is correct
9 Partially correct 67 ms 592 KB Output is partially correct
10 Partially correct 70 ms 592 KB Output is partially correct
11 Partially correct 67 ms 600 KB Output is partially correct
12 Partially correct 140 ms 600 KB Output is partially correct