QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #585917 | #9252. Penguins in Refrigerator | mocania | WA | 47ms | 79664kb | C++14 | 2.8kb | 2024-09-23 22:57:25 | 2024-09-23 22:57:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7,p=1e9+7; priority_queue<int>Q;
int n,q,sum=1,f[N],w[N],e[N],st[N],l[N],r[N],Lx[N],Rx[N],sz[N],op[N],og[N],cnt[N]; unordered_map<int,int>C; vector<int>v[N],s[N];
void A(int a,int b){
for(int i=b;i>=1;i--) sum=1ll*sum*(a-i+1)%p;
}
void dfs(int u){
og[u]+=op[u];
// cout<<u<<":"<<op[u]<<endl;
for(int x:s[u]){
// cout<<u<<":"<<x<<endl;
dfs(x),og[u]+=og[x];
}
A(og[u],op[u]);
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>q;
for(int i=n;i>=1;i--) cin>>f[i];
for(int i=1;i<=n;i++) cin>>w[i],e[i]=w[i];
sort(e+1,e+n+1); int sx=e[n]+e[n-1];
if(sx<=q){
int ans=1;
for(int i=1;i<=n;i++) ans=1ll*ans*i%p;
cout<<ans<<endl;
for(int i=1;i<=n;i++) cout<<i<<" "; cout<<endl; return 0;
}
for(int i=1;i<=n;i++) C[e[i]]=i;
for(int i=1;i<=n;i++) e[i]=C[w[i]]--;
e[0]=n+1,st[0]=0;
for(int i=1;i<=n;i++){
while(st[0]>0&&e[f[st[st[0]]]]<e[f[i]]) st[0]--; l[i]=st[st[0]];
if(st[0]>0&&w[f[st[1]]]+w[f[i]]>q){
int L=1,R=st[0],pos=0;
while(L<=R){
int d=(L+R)/2;
if(w[f[st[d]]]+w[f[i]]>q) pos=st[d],Lx[i]=st[d+1],L=d+1; else R=d-1;
}
if(w[f[st[st[0]]]]+w[f[i]]>q) Lx[i]=0;
v[f[pos]].push_back(f[i]);
}
else if(st[0]!=0) Lx[i]=st[1];
// if(i==3) cout<<Lx[i]<<","<<st[0]<<","<<endl;
st[++st[0]]=i;
}
st[0]=0;
for(int i=n;i>=1;i--){
while(st[0]>0&&e[f[st[st[0]]]]<e[f[i]]) st[0]--; r[i]=st[st[0]];
if(st[0]>0&&w[f[st[1]]]+w[f[i]]>q){
int L=1,R=st[0],pos=0;
while(L<=R){
int d=(L+R)/2;
if(w[f[st[d]]]+w[f[i]]>q) pos=st[d],Rx[i]=st[d+1],L=d+1; else R=d-1;
}
if(w[f[st[st[0]]]]+w[f[i]]>q) Rx[i]=0;
// cout<<i<<","<<Rx[i]<<"rx"<<endl;
v[f[i]].push_back(f[pos]);
}
else if(st[0]!=0) Rx[i]=st[1];
// if(i==3) cout<<Rx[i]<<","<<st[0]<<endl;
st[++st[0]]=i;
}
// cout<<Rx[3]<<"ssss"<<endl;
st[0]=0;
for(int i=1;i<=n;i++)
for(int j:v[i]) cnt[j]++;
for(int i=1;i<=n;i++) if(!cnt[i]) Q.push(-i); int rt;
for(int i=1;i<=n;i++){
if(!l[i]&&!r[i]){
rt=i; continue;
}
if(e[f[l[i]]]<e[f[r[i]]]) s[l[i]].push_back(i);
else s[r[i]].push_back(i);
// if(Lx[i]==-1&&rt<i) Lx[i]=rt; else if(Lx[i]==-1) Lx[i]=0;
// if(Rx[i]==-1&&rt>i) Rx[i]=rt; else if(Rx[i]==-1) Rx[i]=0;
// if(i==3) cout<<Lx[i]<<","<<Rx[i]<<endl;
if(!f[Lx[i]]&&!f[Rx[i]]) continue;
if(e[f[Lx[i]]]<e[f[Rx[i]]]) op[Lx[i]]++;
// cout<<i<<":"<<Lx[i]<<endl;
else op[Rx[i]]++;
// cout<<i<<":"<<Rx[i]<<endl;
// cout<<i<<","<<Lx[i]<<","<<Rx[i]<<endl;
}
for(int i=1;i<=n;i++) if((!Lx[i]&&!Rx[i])||i==rt) og[i]=1;
dfs(rt);
cout<<sum<<endl;
for(int i=1;i<=n;i++){
int x=-Q.top(); Q.pop();
printf("%d ",x);
for(int j:v[x]){
cnt[j]--;
if(!cnt[j]) Q.push(-j);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 72120kb
input:
5 10 1 2 3 4 5 6 5 3 9 2
output:
3 5 4 2 1 3
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 8ms
memory: 71984kb
input:
5 10 1 2 3 4 5 2 4 3 3 8
output:
30 1 5 2 3 4
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 8ms
memory: 58184kb
input:
5 10 1 2 3 4 5 2 3 4 5 1
output:
120 1 2 3 4 5
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 9ms
memory: 70444kb
input:
5 10 1 2 3 4 5 2 3 4 5 6
output:
60 1 2 3 5 4
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 23ms
memory: 57628kb
input:
100000 96 1996 78922 45321 68844 32404 82013 66552 81163 17216 48170 35495 56660 13480 43118 23173 47257 50168 87069 26167 67231 31758 25694 61063 56642 8923 7727 54528 96554 38964 7604 6822 16256 45300 58869 31359 48638 87645 14779 81505 59585 89293 9291 7002 31810 84701 77648 78295 42595 11394 479...
output:
457992974 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 10...
result:
ok 2 lines
Test #6:
score: -100
Wrong Answer
time: 47ms
memory: 79664kb
input:
100000 84 93330 3894 94859 22134 49668 30606 26739 82976 76701 56323 75537 7626 87226 20857 98177 21811 70827 75898 8111 48223 26186 64222 63002 79024 19126 41638 1048 43857 25379 19764 60207 27675 77665 66327 6274 34861 30287 13449 64505 51490 5804 65843 49014 85795 12365 31565 34411 71697 66568 28...
output:
730391126 1723 2800 15421 26278 31659 42502 42606 56945 60694 62369 70160 73990 80586 88502 89122 59690 27661 33622 94788 14089 1146 2690 3632 4491 5439 8588 17476 17922 18136 20123 24857 39523 18825 28520 30999 32947 36013 41413 43842 43919 54502 58104 60783 65767 69064 71878 74728 75343 76546 7807...
result:
wrong answer 1st lines differ - expected: '524727018', found: '730391126'