QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#231426#6561. Fail FastfickleML 1ms6056kbC++201.6kb2023-10-29 11:21:042023-10-29 11:21:05

Judging History

你现在查看的是最新测评结果

  • [2023-10-29 11:21:05]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:6056kb
  • [2023-10-29 11:21:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))

typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
#define log(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }

constexpr int N = 100100;

int n, f[N], g[N], ged[N], fa[N], v[N]; db c[N], p[N];
struct node {
	db c, p; int id;
	node(db c_=0, db p_=0, int id_=0) :
		c(c_), p(p_), id(id_) {}
};
bool operator<(const node &a, const node &b) {
	return a.c * (1 - b.p) > b.c * (1 - a.p);
}
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
signed main() {
	atexit([](){cerr << "time: " << (db)clock()/CLOCKS_PER_SEC << "s\n";});
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	priority_queue<node> q;
	for(int i = 1; i <= n; i++) {
		cin >> c[i] >> p[i] >> fa[i];
		q.emplace(c[i], p[i], i);
		f[i] = i, ged[i] = i;
	}
	v[0] = 1;
	vi ans;
	while(SZ(q)) {
		auto [ci, pi, id] = q.top(); q.pop();
		if(c[id] != ci || p[id] != pi) continue;
		int fz = find(fa[id]);
		if(v[fz]) {
			for(int x = id; x; x = g[x])
				ans.pb(x);
			v[id] = 1;
		} else {
			c[fz] = c[fz] + c[id] * p[fz];
			p[fz] = p[fz] * p[id];
			f[id] = fz;
			g[ged[fz]] = id;
			ged[fz] = ged[id];
			q.emplace(c[fz], p[fz], fz);
		}
	}
	for(int i : ans) cout << i << '\n';
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 6056kb

input:

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

output:

4
1
2
3

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 5940kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

2
1
3
4

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

10
18 0.574073 0
13 0.540309 0
13 0.539018 2
12 0.572910 2
15 0.570616 4
16 0.510215 3
17 0.504083 5
19 0.539297 1
19 0.577271 7
10 0.578346 1

output:

2
4
3
6
5
7
1
10
8
9

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 6032kb

input:

20
93 0.093030 0
53 0.056639 0
39 0.021549 0
48 0.069268 3
58 0.009572 4
22 0.015083 1
27 0.024351 5
68 0.085055 7
48 0.031563 5
46 0.025067 9
15 0.095445 2
57 0.011233 6
97 0.028239 2
8 0.060758 6
59 0.097330 13
34 0.052120 3
73 0.055127 11
53 0.004135 12
24 0.051183 5
56 0.027001 13

output:

3
16
4
2
11
5
19
7
9
10
8
17
1
6
14
12
18
13
20
15

result:

ok correct

Test #5:

score: 0
Accepted
time: 1ms
memory: 5992kb

input:

20
971329 0.076234 0
996879 0.012978 0
994191 0.056803 0
978400 0.080792 1
907508 0.008858 4
992071 0.057419 2
901661 0.089621 6
912521 0.051943 5
979169 0.040201 5
904759 0.083405 7
928478 0.092658 7
980034 0.054747 3
906344 0.053231 10
907474 0.090196 8
927695 0.023153 4
995464 0.009387 2
984650 0...

output:

2
16
6
7
10
13
17
19
20
11
1
4
5
15
8
14
18
9
3
12

result:

ok correct

Test #6:

score: 0
Accepted
time: 1ms
memory: 6052kb

input:

20
54 0.952741 0
41 0.912397 0
11 0.963309 0
66 0.915806 3
47 0.919191 4
51 0.906473 5
24 0.989650 6
97 0.964070 7
56 0.997215 1
39 0.981950 2
50 0.994037 2
92 0.942000 7
97 0.900405 3
53 0.950071 6
16 0.980631 14
63 0.950876 10
49 0.995183 15
20 0.908520 5
71 0.949757 16
76 0.972330 9

output:

3
2
4
5
18
6
13
14
15
1
10
16
19
7
12
8
9
20
11
17

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 6056kb

input:

20
933154 0.904059 0
929160 0.911627 0
999437 0.921760 0
991335 0.904136 1
903530 0.943148 4
904464 0.921035 2
944382 0.912394 6
990971 0.982189 7
941308 0.959290 4
993916 0.945081 7
924496 0.989350 1
938782 0.958578 4
964442 0.997198 11
964358 0.938647 10
911972 0.943888 5
975140 0.993873 4
995611 ...

output:

1
4
2
6
7
3
5
15
10
14
20
12
19
9
11
13
17
8
18
16

result:

ok correct

Test #8:

score: 0
Accepted
time: 1ms
memory: 5992kb

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: -100
Memory Limit Exceeded

input:

100000
938188 0.740681 0
575610 0.965656 1
937341 0.842524 2
817797 0.945396 3
602563 0.818956 4
893939 0.900203 5
952148 0.810399 6
538333 0.960769 7
550079 0.908188 8
676338 0.795726 9
546675 0.529045 10
542108 0.581119 11
963201 0.665127 12
564484 0.897025 13
504952 0.844118 14
673675 0.777947 15...

output:


result: