답안 #944418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944418	2024-03-12T17:30:31 Z	daoquanglinh2007	Nicelines (RMI20_nicelines)	C++17	56.2565 / 100	58 ms	860 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 = 40;

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) 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	436 KB	Output is correct
2	Correct	1 ms	444 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	440 KB	Output is correct
2	Correct	1 ms	448 KB	Output is correct
3	Correct	1 ms	440 KB	Output is correct
4	Correct	2 ms	436 KB	Output is correct

Subtask #3

0.0 / 7.0

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

Subtask #4

11.9453740354 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	46 ms	860 KB	Output is partially correct
2	Partially correct	48 ms	448 KB	Output is partially correct
3	Partially correct	58 ms	688 KB	Output is partially correct
4	Partially correct	58 ms	684 KB	Output is partially correct

Subtask #5

20.3110752233 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	17 ms	448 KB	Output is partially correct
2	Partially correct	16 ms	448 KB	Output is partially correct
3	Partially correct	17 ms	448 KB	Output is partially correct
4	Partially correct	15 ms	704 KB	Output is partially correct

Subtask #6

0.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	46 ms	860 KB	Output is partially correct
2	Partially correct	48 ms	448 KB	Output is partially correct
3	Partially correct	58 ms	688 KB	Output is partially correct
4	Partially correct	58 ms	684 KB	Output is partially correct
5	Partially correct	17 ms	448 KB	Output is partially correct
6	Partially correct	16 ms	448 KB	Output is partially correct
7	Partially correct	17 ms	448 KB	Output is partially correct
8	Partially correct	15 ms	704 KB	Output is partially correct
9	Incorrect	52 ms	448 KB	Incorrect
10	Halted	0 ms	0 KB	-