oj.uz

Submission #592514

# Submission time Handle Problem Language Result Execution time Memory
592514 2022-07-09T09:18:22 Z dantoh000 Nicelines (RMI20_nicelines) C++14
86.7101 / 100
 63 ms 712 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;
ll X = 20001;
void dnc(ll L, ll R, ld S, ld E){
	///printf("DNC %lld %lld %Lf %Lf\n",L,R,S,E);
	if (abs(S-E) < 1e-5){
		return;
	}
	if (L >= R) 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;
    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 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 300 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 3 ms 316 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 2 ms 208 KB Output is correct

Subtask #3
7.0 / 7.0

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

Subtask #4
14.8622838084 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 532 KB Output is partially correct
2 Partially correct 48 ms 544 KB Output is partially correct
3 Partially correct 44 ms 524 KB Output is partially correct
4 Partially correct 46 ms 512 KB Output is partially correct

Subtask #5
21.3779224838 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 328 KB Output is partially correct
2 Partially correct 17 ms 392 KB Output is partially correct
3 Partially correct 13 ms 356 KB Output is partially correct
4 Partially correct 19 ms 304 KB Output is partially correct

Subtask #6
19.4699312361 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 532 KB Output is partially correct
2 Partially correct 48 ms 544 KB Output is partially correct
3 Partially correct 44 ms 524 KB Output is partially correct
4 Partially correct 46 ms 512 KB Output is partially correct
5 Partially correct 15 ms 328 KB Output is partially correct
6 Partially correct 17 ms 392 KB Output is partially correct
7 Partially correct 13 ms 356 KB Output is partially correct
8 Partially correct 19 ms 304 KB Output is partially correct
9 Partially correct 46 ms 508 KB Output is partially correct
10 Partially correct 60 ms 588 KB Output is partially correct
11 Partially correct 58 ms 712 KB Output is partially correct
12 Partially correct 63 ms 564 KB Output is partially correct