oj.uz

답안 #592568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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