Submission #967971

#	Time	Username	Problem	Language	Result	Execution time	Memory
967971		owoovo	Binaria (CCO23_day1problem1)	C++17	25 / 25	265 ms	38992 KiB

Main

#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<=1000000;i++){
        pre[i]=(pre[i-1]*i)%p;
        erp[i]=inv(pre[i]);
    }
    for(int i=0;i<n-k+1;i++){
        cin>>x[i];
    }
    for(int i=0;i<n-k;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: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7