Submission #967934

#	Time	Username	Problem	Language	Result	Execution time	Memory
967934		LittleOrange	Binaria (CCO23_day1problem1)	C++17	25 / 25	90 ms	16208 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e6+3;
ll rev(ll x){
    ll r = 1,p=mod-2;
    while(p){
        if(p&1) r = r*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n-k+1);
    for(ll &i : a) cin >> i;
    vector<ll> b(n,-1);
    for(ll i = 1;i<n-k+1;i++){
        if (a[i]<a[i-1]){
            b[i-1] = 1;
            b[i+k-1] = 0;
        }else if (a[i]>a[i-1]){
            b[i-1] = 0;
            b[i+k-1] = 1;
        }else{

        }
    }
    for(ll i = n-1;i>=k;i--){
        if (b[i]!=-1&&b[i-k]==-1) b[i-k] = b[i];
    }
    ll c1= 0,c0=0;
    for(ll i = 0;i<k;i++){
        c1 += b[i]==1;
        c0 += b[i]==0;
    }
    ll tot = k-c1-c0;
    ll w = a[0]-c1;
    ll ans = 1;
    for(ll i = 1;i<=w;i++){
        ans = ans*rev(i)%mod*(tot-i+1)%mod;
    }
    cout << ans << "\n";
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7