oj.uz

Submission #402079

# Submission time Handle Problem Language Result Execution time Memory
402079 2021-05-11T09:35:21 Z maximath_1 Nicelines (RMI20_nicelines) C++11
92.9931 / 100
 74 ms 564 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;

#define ll long long
#define ld long double
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();
	if(subtask_id == 4) lim = 500;

	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 *= 8;
		}

		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 2 ms 288 KB Output is correct
2 Correct 3 ms 308 KB Output is correct
3 Correct 1 ms 352 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 200 KB Output is correct
2 Correct 3 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 3 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
17.258168369 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 31 ms 372 KB Output is partially correct
2 Partially correct 35 ms 320 KB Output is partially correct
3 Partially correct 31 ms 328 KB Output is partially correct
4 Partially correct 28 ms 376 KB Output is partially correct

Subtask #5
22.204896854 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 288 KB Output is partially correct
2 Partially correct 17 ms 336 KB Output is partially correct
3 Partially correct 18 ms 340 KB Output is partially correct
4 Partially correct 16 ms 328 KB Output is partially correct

Subtask #6
22.530006252 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 31 ms 372 KB Output is partially correct
2 Partially correct 35 ms 320 KB Output is partially correct
3 Partially correct 31 ms 328 KB Output is partially correct
4 Partially correct 28 ms 376 KB Output is partially correct
5 Partially correct 10 ms 288 KB Output is partially correct
6 Partially correct 17 ms 336 KB Output is partially correct
7 Partially correct 18 ms 340 KB Output is partially correct
8 Partially correct 16 ms 328 KB Output is partially correct
9 Partially correct 63 ms 564 KB Output is partially correct
10 Partially correct 29 ms 468 KB Output is partially correct
11 Partially correct 47 ms 440 KB Output is partially correct
12 Partially correct 74 ms 420 KB Output is partially correct