oj.uz

Submission #402077

# Submission time Handle Problem Language Result Execution time Memory
402077 2021-05-11T09:32:40 Z maximath_1 Nicelines (RMI20_nicelines) C++11
92.218 / 100
 52 ms 448 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;

#define ll long long
#define ld long double
const ll lim = 10000;
const ld eps = 1e-6;
map<pair<ll, ll>, ld> mp;
vector<int> a, b;

ld que(ll x, ll y){
	if(mp.count({x, y})) return mp[{x, y}];
	return mp[{x, y}] = query(x, y);
}

ll dv(ll a, ll b){
	if(a < 0) return (a - b + 1) / b;
	return a / b;
}

void solve(int subtask_id, int N){
	mp.clear();

	ll x = lim * 2 + 1, y = x * lim + lim;
	ld diff = que(x, -y + 1) - que(x, -y);
	ll last = -y;

	for(int i = 0; i < N; i ++){
		ll lf = 1, rg = lim;
		while(fabs(que(x, last + rg) - (que(x, last) + rg * diff)) < eps){
			diff = (que(x, last + rg) - que(x, last)) / rg;
			rg *= 4;
		}

		for(ll md; lf < rg;){
			md = (lf + rg) / 2;
			if(fabs(que(x, last + md) - (que(x, last) + md * diff)) < eps) lf = md + 1;
			else rg = md;
		}

		last += lf - 1;
		a.push_back((int)dv(last + lim, x));
		b.push_back((int)(last - a.back() * x));

		diff = que(x, last + 1) - que(x, last);
	}

	the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
16.6443008954 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 428 KB Output is partially correct
2 Partially correct 38 ms 436 KB Output is partially correct
3 Partially correct 42 ms 404 KB Output is partially correct
4 Partially correct 40 ms 392 KB Output is partially correct

Subtask #5
22.1579287357 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 328 KB Output is partially correct
2 Partially correct 11 ms 320 KB Output is partially correct
3 Partially correct 24 ms 316 KB Output is partially correct
4 Partially correct 17 ms 328 KB Output is partially correct

Subtask #6
22.415794956 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 30 ms 428 KB Output is partially correct
2 Partially correct 38 ms 436 KB Output is partially correct
3 Partially correct 42 ms 404 KB Output is partially correct
4 Partially correct 40 ms 392 KB Output is partially correct
5 Partially correct 17 ms 328 KB Output is partially correct
6 Partially correct 11 ms 320 KB Output is partially correct
7 Partially correct 24 ms 316 KB Output is partially correct
8 Partially correct 17 ms 328 KB Output is partially correct
9 Partially correct 42 ms 436 KB Output is partially correct
10 Partially correct 46 ms 428 KB Output is partially correct
11 Partially correct 50 ms 400 KB Output is partially correct
12 Partially correct 52 ms 448 KB Output is partially correct