oj.uz

답안 #592558

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

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

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

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

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

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

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