QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185648#6561. Fail FastfryanWA 250ms22988kbC++144.0kb2023-09-22 13:57:052023-09-22 13:57:06

Judging History

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

  • [2023-09-22 13:57:06]
  • 评测
  • 测评结果:WA
  • 用时:250ms
  • 内存:22988kb
  • [2023-09-22 13:57:05]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <immintrin.h>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
using namespace std;

//numbers
using ll=long long;
#define int ll
using ld=long double;
//pairs
#define P pair
#define pi P<int,int>
#define f first
#define s second
#define mp make_pair
//std data structure
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
//vectors
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vsi V<si>
#define vb V<bool>
#define pb push_back
//sets
#define S set
#define MS multiset
#define US unordered_set
#define si S<int>
#define msi MS<int>
#define usi US<int>
#define ins insert
#define era erase
//maps
#define M map
#define UM unordered_map
#define mii M<int,int>
#define mivi UM<int,vi>
#define misi UM<int,si>
#define umii UM<int,int>
#define umivi UM<int,vi>
#define umisi UM<int,si>
//queues
#define Q queue
#define PQ priority_queue
#define qi Q<int>
#define qpi Q<pi>
#define pqi PQ<int>
#define rpqi PQ<int,vi,greater<int> >
#define pqpi PQ<pi>
#define rpqpi PQ<pi,vpi,greater<pi> >
#define pp P<ld, P< P<ld,ld>, pi > >
//constants
const int MOD=998244353;
const int INF=922337203685477580;
//nt functions
int binpow(int a, int b, int m=MOD) {
    a%=m; int res=1;
    while (b>0) {
        if (b&1) res=res*a%m;
        a=a*a%m;
        b>>=1;
    }
    return res;
}
int gcd (int a, int b) {
    return b?gcd (b,a%b):a;
}
int lcm (int a, int b) {
    return a/gcd(a,b)*b;
}
int inv(int i, int m=MOD) {
	return binpow(i, m-2, m);
}

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool same_set(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {x = get(x), y = get(y);if (x == y) return false;if (e[x] > e[y]) swap(x, y);e[x] += e[y]; e[y] = x;return true;}
};

struct ccpp {
	bool operator() (pp o1, pp o2) {
		return true;
	}
};

ld calc(P<ld,ld> x) {
	ld ret=x.f/((ld)1-x.s); return ret;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n; cin>>n;
	V<pp> ts(n+1);
	for (int i=1; i<=n; i++) {
		cin>>ts[i].s.f.f>>ts[i].s.f.s>>ts[i].s.s.f;
		ts[i].s.s.s=i; ts[i].f=calc(ts[i].s.f);
	}
	vi bk(n+1,0);
	vi bk2(n+1,0);
	vb vis(n+1,0);
	DSU dsu(n+1);
	S<pp> ord;
	for (int i=1; i<=n; i++) {
		ord.ins(ts[i]);
		bk[i]=i; bk2[i]=i;
	}
	
	/*for (int i=1; i<=n; i++) {
		cout<<ts[i].f<<" "<<ts[i].s.f.f<<" "<<ts[i].s.f.s<<"\n";
	}
	cout<<"--------\n";*/
	
	while (!ord.empty()) {
		pp t=*(ord.begin()); ord.era(t);
		ld c=t.s.f.f; ld p=t.s.f.s;
		int d=t.s.s.f; int i=t.s.s.s;
		
//		cout<<c<<" "<<p<<" "<<d<<" "<<i<<"\n";
		
		if (d==0 || vis[d]) {
			int cp=i;
			while (!vis[cp]) {
				vis[cp]=1;
				cout<<cp<<"\n";
				cp=bk[cp];
			}
			continue;
		}
		bk[bk2[dsu.get(d)]]=i;
		bk2[dsu.get(d)]=bk2[dsu.get(i)];
		dsu.unite(i,d);
		pp nd;
		ord.era(ts[d]);
		nd.s.f.f=ts[d].s.f.f+ts[d].s.f.s*c;
		nd.s.f.s=ts[d].s.f.s*p;
		nd.f=calc(nd.s.f);
		nd.s.s.f=ts[d].s.s.f;
		nd.s.s.s=ts[d].s.s.s;
		ts[d]=nd;
		ord.ins(nd);
	}
	
	/*for (int i=1; i<=n; i++) {
		cout<<ts[i].f<<" "<<ts[i].s.f.f<<" "<<ts[i].s.f.s<<"\n";
	}*/
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3720kb

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

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

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

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

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

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

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

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

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

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

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

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

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

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: 0
Accepted
time: 250ms
memory: 22844kb

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok correct

Test #13:

score: 0
Accepted
time: 57ms
memory: 22988kb

input:

100000
501234 0.500516 0
501214 0.503354 1
501013 0.504058 2
502546 0.502962 3
500273 0.505433 4
500197 0.505874 5
505941 0.500204 6
500455 0.506393 7
506433 0.500626 8
503652 0.503861 9
500935 0.507151 10
501370 0.506725 11
502595 0.506236 12
503444 0.505698 13
501723 0.508031 14
505738 0.504150 15...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok correct

Test #14:

score: 0
Accepted
time: 132ms
memory: 22796kb

input:

100000
768956 0.999996 0
686063 0.999982 1
817790 0.999964 2
897069 0.999958 3
940413 0.999956 4
879098 0.999957 5
687880 0.999964 6
663602 0.999959 7
816976 0.999944 8
572136 0.999958 9
653227 0.999946 10
972448 0.999914 11
836815 0.999920 12
617305 0.999941 13
934633 0.999903 14
757071 0.999917 15...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
...

result:

ok correct

Test #15:

score: 0
Accepted
time: 142ms
memory: 22872kb

input:

100000
686602 0.755750 0
606835 0.951986 0
713656 0.504635 0
609527 0.663061 0
752558 0.613758 0
997011 0.880758 0
905135 0.574450 0
732880 0.774286 0
573515 0.609711 0
899010 0.630653 0
664787 0.949029 0
649162 0.965284 0
582075 0.957310 0
939848 0.848816 0
743139 0.738017 0
577134 0.723893 0
91476...

output:

253
67
161
137
179
1001
287
255
3403
97013
304
33
428
135
212
344
237
110
234
35
149
2447
65686
7360
281
267
357
235
11969
10350
55117
23101
44394
90
345
32287
94695
21214
188
5602
3
12430
219
17907
55
71206
152
87789
70
305
9
90656
238
210
5552
72776
32
6029
60929
205
236
6216
249
2763
5064
1136
64...

result:

ok correct

Test #16:

score: -100
Wrong Answer
time: 136ms
memory: 22856kb

input:

100000
866461 0.563475 0
566909 0.892585 1
794999 0.608805 1
572103 0.501998 1
889513 0.669248 4
712553 0.620050 3
721255 0.898776 3
731219 0.870250 5
958886 0.933100 5
946557 0.758386 1
829823 0.901169 6
513249 0.679404 6
707379 0.965023 2
686267 0.691424 13
790432 0.772695 3
630098 0.867609 11
975...

output:

1
4
255
1463
17335
2114
14926
17157
19416
25749
33301
67686
25657
190
2096
37605
50425
2
43930
34070
382
35
1243
11751
70
4349
739
5234
2679
10128
14274
10413
30407
49724
94468
92693
98817
28424
41338
220
4584
702
10034
40074
1056
79762
2754
5745
5840
61325
61426
32441
3
6
12
9550
123
1113
15255
265...

result:

wrong answer your plan is not optimal