QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#134532#6561. Fail FastNoobie_99#TL 1ms3768kbC++201.3kb2023-08-03 22:51:402023-08-03 22:51:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 22:51:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3768kb
  • [2023-08-03 22:51:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define tsolve int t; cin >> t; while(t--) solve
#define debug(x) cerr << __LINE__ << ": "#x" = " << (x) << endl
#define nl '\n'
#define all(x) ::begin(x), ::end(x)
#define sz(x) (int)::size(x)
using ll = long long;
using ld = long double;

struct Thing{
	double c, p;
	list<int> rec;
};

Thing combine(Thing a, Thing b){
	Thing c;
	c.c = a.c + a.p*b.c;
	c.p = a.p*b.p;
	a.rec.splice(a.rec.end(), b.rec);
	c.rec = move(a.rec);
	return c;
}
bool operator < (Thing a, Thing b){
	return a.c / (1.0 - a.p) < b.c / (1.0 - b.p);
}

int n;
vector<Thing> w;
vector<vector<int>> g;
set<Thing> ret;

void dfs(int u){
	set<Thing> s;
	for(int v : g[u]){
		dfs(v);
		if(sz(s) < sz(ret)) swap(s, ret);
		for(Thing t : ret) s.insert(t);
	}
	if(u != 0){
		Thing me = w[u];
		while(!s.empty() && *s.begin() < me){
			me = combine(me, *s.begin());
			s.erase(s.begin());
		}
		s.insert(me);
	}
	swap(s, ret);
}

void solve() {
	cin >> n;
	w.resize(n+1),g.resize(n+1);
	for(int i = 1; i <= n; i++){
		double c, p; int d;
		cin >> c >> p >> d;
		w[i].c = c, w[i].p = p; w[i].rec.push_back(i);
		g[d].push_back(i);
	}
	dfs(0);
	for(Thing t : ret){
		for(int i : t.rec) cout << i << "\n";
	}
}
 
int main() {
	cin.tie(0)->sync_with_stdio(false);
	cout << setprecision(16);
	solve();
}

详细

Test #1:

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

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: 3656kb

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: 1ms
memory: 3768kb

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: 3568kb

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: 3660kb

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: 3604kb

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: 1ms
memory: 3744kb

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: 0ms
memory: 3716kb

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

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

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

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

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

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

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: -100
Time 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: