oj.uz

Submission #402073

# Submission time Handle Problem Language Result Execution time Memory
402073 2021-05-11T09:29:35 Z maximath_1 Nicelines (RMI20_nicelines) C++11
0 / 100
 40 ms 364 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){
	return a / b + ((a ^ b) < 0 && 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
0.0 / 11.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 Incorrect 1 ms 200 KB Incorrect
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Incorrect 2 ms 300 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 340 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 364 KB Incorrect
2 Halted 0 ms 0 KB -