oj.uz

답안 #944425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944425 2024-03-12T17:33:38 Z daoquanglinh2007 Nicelines (RMI20_nicelines) C++17
65.0927 / 100
 69 ms 936 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+10, MAX_DEP = 50;

const ld EPS = 1e-9, inf = 1e18;

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){
		if (dep >= 32){
			get(l);
			get(r);
		}
		return;
	}
	dnc(dep+1, l, mid, fl, fmid);
	dnc(dep+1, mid, r, fmid, fr);
}

void solve(int subtask_id, int N){
	va.clear();
	vb.clear();
	dnc(0, -2*LIM*(x0+1), 2*LIM*(x0+1), +inf, +inf);
	the_lines_are(va, vb);
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 444 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 2 ms 684 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 2 ms 692 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 700 KB Output is correct
2 Incorrect 2 ms 452 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #4
9.2016774337 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 64 ms 448 KB Output is partially correct
2 Partially correct 56 ms 688 KB Output is partially correct
3 Partially correct 55 ms 436 KB Output is partially correct
4 Partially correct 53 ms 936 KB Output is partially correct

Subtask #5
19.5159720773 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 17 ms 452 KB Output is partially correct
2 Partially correct 20 ms 448 KB Output is partially correct
3 Partially correct 21 ms 448 KB Output is partially correct
4 Partially correct 17 ms 712 KB Output is partially correct

Subtask #6
12.3750468846 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 64 ms 448 KB Output is partially correct
2 Partially correct 56 ms 688 KB Output is partially correct
3 Partially correct 55 ms 436 KB Output is partially correct
4 Partially correct 53 ms 936 KB Output is partially correct
5 Partially correct 17 ms 452 KB Output is partially correct
6 Partially correct 20 ms 448 KB Output is partially correct
7 Partially correct 21 ms 448 KB Output is partially correct
8 Partially correct 17 ms 712 KB Output is partially correct
9 Partially correct 60 ms 680 KB Output is partially correct
10 Partially correct 67 ms 436 KB Output is partially correct
11 Partially correct 65 ms 680 KB Output is partially correct
12 Partially correct 69 ms 684 KB Output is partially correct