oj.uz

Submission #944468

# Submission time Handle Problem Language Result Execution time Memory
944468 2024-03-12T18:06:37 Z daoquanglinh2007 Nicelines (RMI20_nicelines) C++17
49.8352 / 100
 101 ms 880 KB 
#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
 
const ll LIM = 1e4, x0 = 2*LIM;
 
const ld EPS = 1e-9, inf = 1e18;
 
ll MAX_DEP = 40;
vector <int> va, vb;
set <pii> S;
 
void get(ld y){
	int b = int(round(y+x0*LIM+LIM))%x0-LIM, a = int(round(y-b)/(ld)x0);
	if (!S.count(mp(a, b))){
		va.push_back(a);
		vb.push_back(b);
		S.insert(mp(a, b));
	}
}
 
void dnc(int dep, ld l, ld r, ld fl, ld fr){
	if (dep >= MAX_DEP){
		get(l);
		return;
	}
	ld mid = (l+r)/2.0;
	if (fl == +inf) fl = query(x0, l);
	if (fr == +inf) fr = query(x0, r);
	ld fmid = query(x0, mid);
	if (abs(2.0*fmid - (fl+fr)) <= EPS) return;
	dnc(dep+1, l, mid, fl, fmid);
	dnc(dep+1, mid, r, fmid, fr);
}
 
void solve(int subtask_id, int N){
	while (true){
		va.clear();
		vb.clear();
		S.clear();
		dnc(0, -2*LIM*(x0+1), 2*LIM*(x0+1), +inf, +inf);
		if ((int)va.size() >= N) break;
		MAX_DEP--;
	}
	the_lines_are(va, vb);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
0.0 / 7.0

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

Subtask #4
11.9453740354 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 39 ms 452 KB Output is partially correct
2 Partially correct 50 ms 604 KB Output is partially correct
3 Partially correct 43 ms 704 KB Output is partially correct
4 Partially correct 40 ms 700 KB Output is partially correct

Subtask #5
13.889862472 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 14 ms 700 KB Output is partially correct
2 Partially correct 15 ms 448 KB Output is partially correct
3 Partially correct 44 ms 448 KB Output is partially correct
4 Partially correct 31 ms 700 KB Output is partially correct

Subtask #6
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 39 ms 452 KB Output is partially correct
2 Partially correct 50 ms 604 KB Output is partially correct
3 Partially correct 43 ms 704 KB Output is partially correct
4 Partially correct 40 ms 700 KB Output is partially correct
5 Partially correct 14 ms 700 KB Output is partially correct
6 Partially correct 15 ms 448 KB Output is partially correct
7 Partially correct 44 ms 448 KB Output is partially correct
8 Partially correct 31 ms 700 KB Output is partially correct
9 Incorrect 101 ms 880 KB Incorrect
10 Halted 0 ms 0 KB -