QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#304016	#1191. Reordering the Documents	NYCU_CartesianTree^#	WA	2ms	4240kb	C++20	1.8kb	2024-01-13 11:38:36	2024-01-13 11:38:37

Judging History

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

[2024-01-13 11:38:37]
评测

测评结果：WA
用时：2ms
内存：4240kb

查看

[2024-01-13 11:38:36]
提交

answer

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

#define int long long 
#define F first 
#define S second 
#define pb push_back

const int mol=1e9+7;

vector<int>node[5005];
bool vis[5005];
int dis[5005];
bool ok=1;
int t1=0,t2=0;

void dfs(int v){
    vis[v]=1;
    if(dis[v]==1) t2++;
    else t1++;
    for(int k:node[v]){
        if(!vis[k]) dis[k]=(dis[v]^1),dfs(k);
        else{
            if(dis[k]!=(dis[v]^1)){
                ok=0;
                return;
            }
        }
    }
}

int dp[2][5005];

void solve(){
    int n,m;
    cin>>n>>m;

    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j]){
                node[i].pb(j);
                node[j].pb(i);
            }
        }
    }

    dp[0][0]=1;
    int iu=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            t1=0,t2=0;
            dis[i]=1;
            dfs(i);
        }
        else continue;
        if(!ok){
            cout<<"0\n";
            return;
        }
        if(t1==0){
            for(int j=m;j>=1;j--) dp[iu^1][j]=dp[iu^1][j-1];
            dp[iu^1][0]=0;
            continue;
        }
        for(int j=m;j>=0;j--) dp[iu][j]=0;
        for(int j=m;j>=0;j--){
            if(j-t1>=0)
            dp[iu][j]=dp[iu^1][j-t1];
            if(j-t2>=0)
            dp[iu][j]+=dp[iu^1][j-t2];
            dp[iu][j]%=mol;
        }
        iu^=1;
    }

    iu^=1;
    int ans=0;
    for(int j=m;j>=0;j--){
        if(n-j>m) break;
        ans+=dp[iu][j];
        ans%=mol;
    }
    ans<<=1;
    ans%=mol;
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3636kb

input:

6 3
1 3 4 2 6 5

output:

result:

ok answer is '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

6 6
1 3 4 2 6 5

output:

result:

ok answer is '8'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

4 4
4 3 1 2

output:

result:

ok answer is '0'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3748kb

input:

6 3
1 3 4 2 6 5

output:

result:

ok answer is '4'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

6 6
1 3 4 2 6 5

output:

result:

ok answer is '8'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

4 4
4 3 1 2

output:

result:

ok answer is '0'

Test #7:

score: -100

Wrong Answer

time: 2ms

memory: 4240kb

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:

result:

wrong answer expected '11363968', found '3456'