oj.uz

Submission #402080

# Submission time Handle Problem Language Result Execution time Memory
402080 2021-05-11T09:36:02 Z maximath_1 Nicelines (RMI20_nicelines) C++11
92.8567 / 100
 44 ms 508 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 *= 6;
		}
 
		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 288 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 1 ms 288 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 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 2 ms 200 KB Output is correct
4 Correct 3 ms 200 KB Output is correct

Subtask #4
17.2027401535 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 32 ms 328 KB Output is partially correct
2 Partially correct 26 ms 420 KB Output is partially correct
3 Partially correct 32 ms 328 KB Output is partially correct
4 Partially correct 30 ms 328 KB Output is partially correct

Subtask #5
22.1948322564 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 316 KB Output is partially correct
2 Partially correct 14 ms 332 KB Output is partially correct
3 Partially correct 16 ms 320 KB Output is partially correct
4 Partially correct 17 ms 340 KB Output is partially correct

Subtask #6
22.459116483 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 32 ms 328 KB Output is partially correct
2 Partially correct 26 ms 420 KB Output is partially correct
3 Partially correct 32 ms 328 KB Output is partially correct
4 Partially correct 30 ms 328 KB Output is partially correct
5 Partially correct 17 ms 316 KB Output is partially correct
6 Partially correct 14 ms 332 KB Output is partially correct
7 Partially correct 16 ms 320 KB Output is partially correct
8 Partially correct 17 ms 340 KB Output is partially correct
9 Partially correct 39 ms 480 KB Output is partially correct
10 Partially correct 41 ms 448 KB Output is partially correct
11 Partially correct 43 ms 508 KB Output is partially correct
12 Partially correct 44 ms 468 KB Output is partially correct