QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #35532 | #1191. Reordering the Documents | Appleblue17 | WA | 3ms | 4044kb | C++14 | 1.4kb | 2022-06-16 17:30:05 | 2022-06-16 17:30:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5500,mod=1e9+7;
int n,m,p[N],dp[N],ans;
vector <int> G[N];
int pnt[N],id;
bool vis[N];
void dfs(int u){
if(vis[u]) return ;
pnt[++id]=u;
vis[u]=1;
for(int i=0;i<(int)G[u].size();i++) dfs(G[u][i]);
}
int q[N],ct;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++){
id=0;
for(int j=1;j<i;j++)
if(p[j]>p[i]) pnt[++id]=j;
for(int t=1;t<id;t++)
// cout<<pnt[t]<<" "<<pnt[t+1]<<endl,
G[pnt[t]].push_back(pnt[t+1]),G[pnt[t+1]].push_back(pnt[t]);
}
for(int i=1;i<=n;i++){
id=0;
for(int j=i+1;j<=n;j++)
if(p[j]<p[i]) pnt[++id]=j;
for(int t=1;t<id;t++)
// cout<<pnt[t]<<" "<<pnt[t+1]<<endl,
G[pnt[t]].push_back(pnt[t+1]),G[pnt[t+1]].push_back(pnt[t]);
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
id=0;
dfs(i);
sort(pnt+1,pnt+id+1);
for(int t=1;t<id;t++) if(p[pnt[t]]>p[pnt[t+1]]) return puts("0"),0;
q[++ct]=id;
}
dp[0]=1;
int cur=1;
if(p[1]==1){
dp[q[1]]=1;
cur=2;
}
while(cur<=ct){
if(cur==ct){
for(int i=m;i>=0;i--){
if(i>=q[cur]) dp[i]=(dp[i]+dp[i-q[cur]])%mod;
}
cur++;
continue;
}
for(int i=m;i>=0;i--){
dp[i]=0;
if(i>=q[cur]) dp[i]=dp[i-q[cur]];
if(i>=q[cur+1]) dp[i]=(dp[i]+dp[i-q[cur+1]])%mod;
}
cur+=2;
}
for(int i=n-m;i<=m;i++) ans=(ans+dp[i])%mod;
// for(int i=0;i<=m;i++) cout<<dp[i]<<" ";
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3784kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 4044kb
input:
1000 500 4 5 6 8 10 11 12 13 14 15 20 23 25 26 28 29 33 35 1 2 36 38 3 7 41 9 16 44 48 17 18 51 52 53 19 21 54 22 24 59 61 62 27 67 30 31 32 34 68 69 37 39 73 40 76 77 42 81 83 43 85 45 87 46 89 94 47 95 49 50 97 101 55 103 105 56 57 58 106 60 108 110 63 111 114 64 115 65 119 66 70 71 120 121 72 124...
output:
8192
result:
wrong answer expected '11363968', found '8192'