답안 #944428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944428	2024-03-12T17:35:56 Z	daoquanglinh2007	Nicelines (RMI20_nicelines)	C++17	77.7582 / 100	41 ms	936 KB

nicelines

#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 = 32;
 
const ld EPS = 1e-8, 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) 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	448 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	1 ms	432 KB	Output is correct
4	Correct	1 ms	440 KB	Output is correct

Subtask #2

13.0 / 13.0

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

Subtask #3

0.0 / 7.0

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

Subtask #4

14.1625026041 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	28 ms	936 KB	Output is partially correct
2	Partially correct	40 ms	448 KB	Output is partially correct
3	Partially correct	30 ms	700 KB	Output is partially correct
4	Partially correct	28 ms	688 KB	Output is partially correct

Subtask #5

21.1162429669 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	12 ms	448 KB	Output is partially correct
2	Partially correct	12 ms	448 KB	Output is partially correct
3	Partially correct	12 ms	688 KB	Output is partially correct
4	Partially correct	14 ms	616 KB	Output is partially correct

Subtask #6

18.4794436341 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	28 ms	936 KB	Output is partially correct
2	Partially correct	40 ms	448 KB	Output is partially correct
3	Partially correct	30 ms	700 KB	Output is partially correct
4	Partially correct	28 ms	688 KB	Output is partially correct
5	Partially correct	12 ms	448 KB	Output is partially correct
6	Partially correct	12 ms	448 KB	Output is partially correct
7	Partially correct	12 ms	688 KB	Output is partially correct
8	Partially correct	14 ms	616 KB	Output is partially correct
9	Partially correct	37 ms	452 KB	Output is partially correct
10	Partially correct	41 ms	648 KB	Output is partially correct
11	Partially correct	36 ms	680 KB	Output is partially correct
12	Partially correct	40 ms	680 KB	Output is partially correct