QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153201 | #6561. Fail Fast | qzez# | TL | 210ms | 89484kb | C++14 | 1.6kb | 2023-08-29 16:45:12 | 2023-08-29 16:45:13 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e5+5,M=100+5,K=600+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,To[N],fa[N];
struct Node{
db c;db p;
Node operator +(const Node &B)const{return (Node){c+B.c*(1-p),1-(1-p)*(1-B.p)};}
bool operator <(const Node &B)const{return c/p<B.c/B.p;}
}A[N];
deque<int> q[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
void Solve(){
int i,j;scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%lf%lf%d",&A[i].c,&A[i].p,&To[i]),A[i].p=1-A[i].p,q[i].emplace_back(i);
iota(fa+1,fa+n+1,1);
set<pair<Node,int> > f;
for(i=1;i<=n;i++) f.emplace(A[i],i);
while(!f.empty()){
auto p=*f.begin();f.erase(f.begin());
int ff=GF(To[p.se]);
f.erase(make_pair(A[ff],ff));
A[ff]=A[ff]+A[p.se];
if(q[ff].size()>q[p.se].size()){
while(!q[p.se].empty()) q[ff].emplace_back(q[p.se].front()),q[p.se].pop_front();
} else{
while(!q[ff].empty()) q[p.se].emplace_front(q[ff].back()),q[ff].pop_back();swap(q[ff],q[p.se]);
}
if(ff) f.emplace(A[ff],ff);
}
for(int i:q[0]) printf("%d\n",i);
}
int main(){
int t;
// scanf("%d",&t);
t=1;
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 19ms
memory: 72976kb
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: 18ms
memory: 72692kb
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: 17ms
memory: 73004kb
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: 17ms
memory: 71712kb
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: 14ms
memory: 71896kb
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: 14ms
memory: 71948kb
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: 12ms
memory: 71612kb
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: 19ms
memory: 72328kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 10ms
memory: 71900kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 18ms
memory: 71836kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 12ms
memory: 73356kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: 0
Accepted
time: 210ms
memory: 89484kb
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: -100
Time Limit Exceeded
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...