Submission #1203290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203290		AlgorithmWarrior	Binaria (CCO23_day1problem1)	C++20	25 / 25	193 ms	13892 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e6+5;
int const MOD=1e6+3;
int v[MAX];
int n,k;
int tip[MAX];

void read(){
    cin>>n>>k;
    int i;
    for(i=1;i<=n-k+1;++i)
        cin>>v[i];
}

void restrictions(){
    int i;
    for(i=1;i<=n-k;++i)
    if(v[i]<v[i+1]){
        tip[i]='0';
        tip[i+k]='1';
    }
    else
    if(v[i]>v[i+1]){
        tip[i]='1';
        tip[i+k]='0';
    }
}

void umple(int ind){
    if(ind-k>0 && !tip[ind-k]){
        tip[ind-k]=tip[ind];
        umple(ind-k);
    }
    if(ind+k<=n && !tip[ind+k]){
        tip[ind+k]=tip[ind];
        umple(ind+k);
    }
}

void umplere(){
    int i;
    for(i=1;i<=n;++i)
        if(tip[i])
            umple(i);
}

pair<int,int> rasp(){
    int cnt1=0;
    int cnt2=0;
    int i;
    for(i=1;i<=k;++i){
        if(!tip[i])
            ++cnt1;
        if(tip[i]=='1')
            ++cnt2;
    }
    return {cnt1,v[1]-cnt2};
}

int fact[MAX];

void get_fact(){
    fact[0]=1;
    int i;
    for(i=1;i<MAX;++i)
        fact[i]=1LL*fact[i-1]*i%MOD;
}

int bin_exp(int base,int exp){
    int rez=1;
    while(exp){
        if(exp&1)
            rez=1LL*rez*base%MOD;
        base=1LL*base*base%MOD;
        exp/=2;
    }
    return rez;
}

int comb(int n,int k){
    return 1LL*fact[n]*bin_exp(fact[k],MOD-2)%MOD*bin_exp(fact[n-k],MOD-2)%MOD;
}

void write(int ans){
    cout<<ans;
}

int main()
{
    read();
    restrictions();
    umplere();
    pair<int,int>rsp=rasp();
    get_fact();
    write(comb(rsp.first,rsp.second));
    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