답안 #944439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944439	2024-03-12T17:43:01 Z	daoquanglinh2007	Nicelines (RMI20_nicelines)	C++17	66.7582 / 100	42 ms	868 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;

const ld EPS = 1e-9, inf = 1e18;
 
ll MAX_DEP = 32;
vector <int> va, vb;
set <pii> S;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
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+r)/2.0);
		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){
	if (N <= 3) MAX_DEP = 50;
	va.clear();
	vb.clear();
	dnc(0, -2*LIM*(x0+1), 2*LIM*(x0+1), +inf, +inf);
	the_lines_are(va, vb);
}

Subtask #1

0.0 / 11.0

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

Subtask #2

13.0 / 13.0

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

Subtask #3

0.0 / 7.0

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

Subtask #4

14.1625026041 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	27 ms	692 KB	Output is partially correct
2	Partially correct	32 ms	684 KB	Output is partially correct
3	Partially correct	34 ms	448 KB	Output is partially correct
4	Partially correct	30 ms	704 KB	Output is partially correct

Subtask #5

21.1162429669 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	13 ms	692 KB	Output is partially correct
2	Partially correct	11 ms	456 KB	Output is partially correct
3	Partially correct	11 ms	696 KB	Output is partially correct
4	Partially correct	10 ms	456 KB	Output is partially correct

Subtask #6

18.4794436341 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	27 ms	692 KB	Output is partially correct
2	Partially correct	32 ms	684 KB	Output is partially correct
3	Partially correct	34 ms	448 KB	Output is partially correct
4	Partially correct	30 ms	704 KB	Output is partially correct
5	Partially correct	13 ms	692 KB	Output is partially correct
6	Partially correct	11 ms	456 KB	Output is partially correct
7	Partially correct	11 ms	696 KB	Output is partially correct
8	Partially correct	10 ms	456 KB	Output is partially correct
9	Partially correct	38 ms	868 KB	Output is partially correct
10	Partially correct	42 ms	684 KB	Output is partially correct
11	Partially correct	35 ms	456 KB	Output is partially correct
12	Partially correct	41 ms	448 KB	Output is partially correct