oj.uz

Submission #967967

# Submission time Handle Problem Language Result Execution time Memory
967967 2024-04-23T06:10:45 Z owoovo Binaria (CCO23_day1problem1) C++17
0 / 25
 1 ms 6624 KB 
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
const ll p=1e6+3;
struct Dsu{
    int ori[1000010]={};
    void init(int n){
        for(int i=0;i<=n;i++)ori[i]=i;
    }
    int f(int a){
        if(ori[a]==a)return a;
        ori[a]=f(ori[a]);
        return ori[a];
    }
    void onion(int a,int b){
        a=f(a);
        b=f(b);
        ori[a]=b;
        return ;
    }
}dsu;
int n,k,x[1000010];
ll pre[1000010],erp[1000010];
ll inv(ll a){
    return a==1?1:(p-p/a)*inv(p%a)%p;
}
ll c(ll a,ll b){
    if(a<b)return 0;
    return ((pre[a]*erp[b]%p)*erp[a-b])%p;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    dsu.init(n+1);
    pre[0]=1;
    erp[0]=1;
    for(int i=1;i<=k;i++){
        pre[i]=(pre[i-1]*i)%p;
        erp[i]=inv(pre[i]);
    }
    for(int i=0;i<n-k;i++){
        cin>>x[i];
    }
    for(int i=0;i<n-k-1;i++){
        int f=i+2,b=f+k;
        if(x[i]==x[i+1])dsu.onion(f,b);
        if(x[i]>x[i+1]){
            dsu.onion(f,1);
            dsu.onion(b,0);
        }
        if(x[i]<x[i+1]){
            dsu.onion(f,0);
            dsu.onion(b,1);
        }
    }
    if(dsu.f(0)==dsu.f(1)){
        cout<<"0\n";
        return 0;
    }
    int u=dsu.f(0),v=dsu.f(1);
    int cnt=0,cnt1=0;
    for(int i=2;i<2+k;i++){
        int w=dsu.f(i);
        if(w==v){
            cnt1++;
        }
        if(u!=w&&v!=w){
            cnt++;
        }
    }
    cout<<c(cnt,x[0]-cnt1)<<"\n";
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6496 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6496 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Incorrect 1 ms 6624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6496 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6496 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Incorrect 1 ms 6624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6496 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6496 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Incorrect 1 ms 6624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6496 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6496 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Incorrect 1 ms 6624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6496 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6496 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Incorrect 1 ms 6624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6496 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6496 KB Output is correct
9 Correct 1 ms 6496 KB Output is correct
10 Incorrect 1 ms 6624 KB Output isn't correct
11 Halted 0 ms 0 KB -