oj.uz

Submission #403009

# Submission time Handle Problem Language Result Execution time Memory
403009 2021-05-12T16:17:59 Z maximath_1 Nicelines (RMI20_nicelines) C++11
100 / 100
 9 ms 332 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;

#define ll long long
#define ld long double
const ld eps = 1e-9;
const ll lim = 10000;
const ll x0 = 2 * lim + 1;
const ll inf = lim * lim * 2 + lim * lim;

map<ll, ld> mem;
ld que(ll y){
	if(mem.count(y)) return mem[y];
	return mem[y] = query(x0, (ld)y / 2.0L);
}

pair<ld, ld> get_line(pair<ld, ld> p1, pair<ld, ld> p2){
	return make_pair((p1.second - p2.second) / (p1.first - p2.first), p1.second - p1.first * (p1.second - p2.second) / (p1.first - p2.first));
}

ld intersectionX(pair<ld, ld> l1, pair<ld, ld> l2){
	return (l2.second - l1.second) / (l1.first - l2.first);
}

bool check_eq(ld a, ld b){
	return fabs(a - b) < eps;
}

bool oneline(ll x1, ll x2, ll x3){
	if(x1 == x2 || x2 == x3 || x3 == x1) return true;
	ld y1 = que(x1), y2 = que(x2), y3 = que(x3);
	return check_eq((y2 - y1)/(x2 - x1), (y3 - y2)/(x3 - x2));
}

set<ll> changing_points;
void dnc(ll lf1, ll lf2, ll rg1, ll rg2){
	pair<ld, ld> l_lf = get_line(make_pair(lf1, que(lf1)), make_pair(lf2, que(lf2)));
	pair<ld, ld> l_rg = get_line(make_pair(rg1, que(rg1)), make_pair(rg2, que(rg2)));
	if(check_eq(l_lf.first, l_rg.first)) return;

	ll md = round(intersectionX(l_lf, l_rg));

	if(oneline(lf1, lf2, md) && oneline(md, rg1, rg2)){
		changing_points.insert(md);
	}else{
		dnc(lf1, lf2, md - 1, md);
		dnc(md - 1, md, rg1, rg2);
	}
}

void solve(int subtask_id, int N){
	dnc(2 * (-inf), 2 * (-inf + x0), 2 * inf, 2 * (inf + x0));

	vector<int> a, b;
	for(auto y : changing_points){
		y /= 2;
		ll bb = y % x0;
		while(bb < -lim) bb += x0;
		while(bb > lim) bb -= x0;

		ll aa = (y - bb) / x0;

		a.push_back(aa);
		b.push_back(bb);
	}

	the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.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 #3
7.0 / 7.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 2 ms 200 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 328 KB Output is correct
2 Correct 7 ms 312 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 6 ms 320 KB Output is correct

Subtask #5
23.0 / 23.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 #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 328 KB Output is correct
2 Correct 7 ms 312 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 6 ms 320 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Correct 2 ms 200 KB Output is correct
7 Correct 2 ms 200 KB Output is correct
8 Correct 3 ms 200 KB Output is correct
9 Correct 6 ms 328 KB Output is correct
10 Correct 6 ms 328 KB Output is correct
11 Correct 9 ms 324 KB Output is correct
12 Correct 6 ms 328 KB Output is correct