oj.uz

Submission #592558

# Submission time Handle Problem Language Result Execution time Memory
592558 2022-07-09T09:58:02 Z dantoh000 Nicelines (RMI20_nicelines) C++14
73 / 100
 13 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-10){
		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-10){
			///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("%d diffs\n", (int)round(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 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 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 2 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 #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 592 KB Output is correct
2 Correct 9 ms 600 KB Output is correct
3 Correct 9 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 3 ms 592 KB Output is correct
2 Correct 4 ms 592 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 3 ms 592 KB Output is correct

Subtask #6
0.0 / 27.0

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