답안 #810276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810276	2023-08-06T07:53:26 Z	ymm	Mixture (BOI20_mixture)	C++17	60 / 100	398 ms	39652 KB

Mixture

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

typedef complex<double> pnt;

const double eps = 1e-9;

struct obj {
	pnt P;
	bool first;
	pnt F;
	double argF;
	double mn, mx;
	multiset<double> S;
	bool line;
	bool zero;

	double add(pnt A, double argA)
	{
		if (!first) {
			F = A;
			argF = argA;
			first = 1;
		}
		double theta = argA - argF;
		if (theta > M_PI)
			theta -= 2*M_PI;
		if (theta < -M_PI)
			theta += 2*M_PI;
		S.insert(theta);
		if (abs(A.real()) < eps && abs(A.imag()) < eps) {
			zero = 1;
			return theta;
		}
		mn = min(mn, theta);
		mx = max(mx, theta);
		double theta2 = theta;
		if (theta > 0)
			theta2 -= M_PI;
		else
			theta2 += M_PI;
		auto it = S.lower_bound(theta2-eps);
		if (it != S.end() && *it - theta2 < eps)
			line = 1;
		return theta;
	}

	int get_ans() {
		if (zero)
			return 1;
		if (line)
			return 2;
		if (first && mx - mn > M_PI - eps)
			return 3;
		return 0;
	}
};

struct preprocP {
	pnt P;
	double a;
};

pnt normalize(double x, double y, double z)
{
	double sum = x+y+z;
	x /= sum;
	y /= sum;
	return {x, y};
}

pnt P;
const int N = 100'010;
int n;

namespace seg {
	vector<preprocP> t[N*4];
	void add(int l, int r, const preprocP &P, int i, int b, int e) {
		if (l <= b && e <= r) {
			t[i].push_back(P);
			return;
		}
		if (r <= b || e <= l)
			return;
		add(l, r, P, 2*i+1, b, (b+e)/2);
		add(l, r, P, 2*i+2, (b+e)/2, e);
	}
	void add(int l, int r, pnt P) {
		preprocP Q;
		Q.P = P-::P;
		Q.a = arg(Q.P);
		add(l, r, Q, 0, 0, n);
	}

	void dfs(obj &o0, int i, int b, int e) {
		multiset<double> marg;
		o0.S.swap(marg);
		obj o = o0;
		o.S.swap(marg);
		vector<double> kooft;
		for (auto P : t[i])
			kooft.push_back(o.add(P.P, P.a));
		if (e-b == 1) {
			cout << o.get_ans() << '\n';
		} else {
			dfs(o, 2*i+1, b, (b+e)/2);
			dfs(o, 2*i+2, (b+e)/2, e);
		}
		o.S.swap(marg);
		for (auto x : kooft)
			marg.erase(marg.find(x));
		o0.S.swap(marg);
	}
	void dfs(pnt P) {
		obj o = {};
		o.P = P;
		dfs(o, 0, 0, n);
	}
}

pnt readp()
{
	ll x, y, z;
	cin >> x >> y >> z;
	return normalize(x, y, z);
}

pnt a[N];
int l[N];
bool rem[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	P = readp();
	cin >> n;
	int cnt = 0;
	Loop (i,0,n) {
		char c;
		cin >> c;
		if (c == 'A') {
			a[cnt] = readp();
			l[cnt] = i;
			++cnt;
		} else {
			int x;
			cin >> x;
			--x;
			seg::add(l[x], i, a[x]);
			rem[x] = 1;
		}
	}
	Loop (i,0,cnt) {
		if (!rem[i])
			seg::add(l[i], n, a[i]);
	}
	seg::dfs(P);
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9672 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	4 ms	9684 KB	Output is correct
11	Correct	4 ms	9684 KB	Output is correct
12	Correct	7 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	5 ms	9620 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9672 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	4 ms	9684 KB	Output is correct
11	Correct	4 ms	9684 KB	Output is correct
12	Correct	7 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	5 ms	9620 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9812 KB	Output is correct
24	Correct	5 ms	9816 KB	Output is correct
25	Correct	5 ms	9812 KB	Output is correct
26	Correct	5 ms	9812 KB	Output is correct
27	Correct	5 ms	9684 KB	Output is correct
28	Correct	5 ms	9812 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	5 ms	9684 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	5 ms	9736 KB	Output is correct
33	Correct	5 ms	9684 KB	Output is correct
34	Correct	5 ms	9812 KB	Output is correct
35	Correct	5 ms	9684 KB	Output is correct
36	Correct	5 ms	9684 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9672 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	4 ms	9684 KB	Output is correct
11	Correct	4 ms	9684 KB	Output is correct
12	Correct	7 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	5 ms	9620 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9812 KB	Output is correct
24	Correct	5 ms	9816 KB	Output is correct
25	Correct	5 ms	9812 KB	Output is correct
26	Correct	5 ms	9812 KB	Output is correct
27	Correct	5 ms	9684 KB	Output is correct
28	Correct	5 ms	9812 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	5 ms	9684 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	5 ms	9736 KB	Output is correct
33	Correct	5 ms	9684 KB	Output is correct
34	Correct	5 ms	9812 KB	Output is correct
35	Correct	5 ms	9684 KB	Output is correct
36	Correct	5 ms	9684 KB	Output is correct
37	Correct	5 ms	9684 KB	Output is correct
38	Correct	5 ms	9684 KB	Output is correct
39	Correct	6 ms	9812 KB	Output is correct
40	Correct	6 ms	9812 KB	Output is correct
41	Correct	7 ms	9812 KB	Output is correct
42	Correct	7 ms	9812 KB	Output is correct
43	Correct	6 ms	9812 KB	Output is correct
44	Correct	7 ms	9812 KB	Output is correct
45	Correct	6 ms	9812 KB	Output is correct
46	Correct	11 ms	10460 KB	Output is correct
47	Correct	11 ms	10460 KB	Output is correct
48	Correct	6 ms	9812 KB	Output is correct
49	Correct	8 ms	10068 KB	Output is correct
50	Correct	9 ms	10068 KB	Output is correct
51	Correct	14 ms	10628 KB	Output is correct
52	Correct	15 ms	10992 KB	Output is correct
53	Correct	15 ms	10964 KB	Output is correct
54	Correct	18 ms	10960 KB	Output is correct
55	Correct	12 ms	10660 KB	Output is correct
56	Correct	14 ms	10604 KB	Output is correct

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9672 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9732 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	4 ms	9684 KB	Output is correct
11	Correct	4 ms	9684 KB	Output is correct
12	Correct	7 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	5 ms	9620 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9812 KB	Output is correct
24	Correct	5 ms	9816 KB	Output is correct
25	Correct	5 ms	9812 KB	Output is correct
26	Correct	5 ms	9812 KB	Output is correct
27	Correct	5 ms	9684 KB	Output is correct
28	Correct	5 ms	9812 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	5 ms	9684 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	5 ms	9736 KB	Output is correct
33	Correct	5 ms	9684 KB	Output is correct
34	Correct	5 ms	9812 KB	Output is correct
35	Correct	5 ms	9684 KB	Output is correct
36	Correct	5 ms	9684 KB	Output is correct
37	Correct	5 ms	9684 KB	Output is correct
38	Correct	5 ms	9684 KB	Output is correct
39	Correct	6 ms	9812 KB	Output is correct
40	Correct	6 ms	9812 KB	Output is correct
41	Correct	7 ms	9812 KB	Output is correct
42	Correct	7 ms	9812 KB	Output is correct
43	Correct	6 ms	9812 KB	Output is correct
44	Correct	7 ms	9812 KB	Output is correct
45	Correct	6 ms	9812 KB	Output is correct
46	Correct	11 ms	10460 KB	Output is correct
47	Correct	11 ms	10460 KB	Output is correct
48	Correct	6 ms	9812 KB	Output is correct
49	Correct	8 ms	10068 KB	Output is correct
50	Correct	9 ms	10068 KB	Output is correct
51	Correct	14 ms	10628 KB	Output is correct
52	Correct	15 ms	10992 KB	Output is correct
53	Correct	15 ms	10964 KB	Output is correct
54	Correct	18 ms	10960 KB	Output is correct
55	Correct	12 ms	10660 KB	Output is correct
56	Correct	14 ms	10604 KB	Output is correct
57	Correct	15 ms	10968 KB	Output is correct
58	Correct	16 ms	10964 KB	Output is correct
59	Correct	16 ms	10964 KB	Output is correct
60	Correct	16 ms	11024 KB	Output is correct
61	Correct	54 ms	15428 KB	Output is correct
62	Correct	53 ms	15360 KB	Output is correct
63	Correct	376 ms	39568 KB	Output is correct
64	Correct	398 ms	39652 KB	Output is correct
65	Incorrect	320 ms	33180 KB	Output isn't correct
66	Halted	0 ms	0 KB	-

답안 #810276

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 30.0 / 30.0

Subtask #4 0 / 40.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
30.0 / 30.0

Subtask #4
0 / 40.0