Submission #1305983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305983		nasjes	Binaria (CCO23_day1problem1)	C++20	25 / 25	152 ms	39572 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

typedef long double ld;
const ll dim=1e6 + 10;
const ll mod=1e6+3;
const ll inf=1e18+77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n,t, k;
ll a[dim];
vector<pll> subs;
ll same[dim];
ll fc[dim], ufc[dim];
ll binpow(ll a, ll p){
    ll r=1;
    while(p>0){
        if(p&1){
            p--;
            r*=a;
            r=r%mod;
        }
        a=(a*a)%mod;
        p/=2;
    }
    return r%mod;
}


ll cnt(ll k, ll n){
    ll zn=(ufc[k]*ufc[n-k])%mod;
    ll ch=fc[n];
    ch=(ch*zn)%mod;
    return ch;
}
ll f[dim];
ll b[dim];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //cin>>t;
    fc[0]=1;
    ufc[0]=1;
    for(int i=1; i<=1e6; i++){
        fc[i]=fc[i-1]*i;
        fc[i]=(fc[i]%mod);
        ufc[i]=binpow(fc[i], mod-2);
    }
    t=1;
    while(t--){

        cin>>n>>k;
        for(int i=1; i<=n-k+1; i++){
            cin>>a[i];
        }
        for(int i=1; i<=n; i++)b[i]=-1;
        ll fl=1;
        for(int i=2; i<=n-k+1; i++){
            if(a[i]==a[i-1]){
                same[i+k-1]=0;
            }
            else if(a[i]==a[i-1]-1){
                same[i+k-1]=-1;
            }
            else if(a[i]==a[i-1]+1){
                same[i+k-1]=1;
            }
            else{
                fl=0;
            }
        }
        for(int i=1; i<=k; i++){
            f[i]=1;
        }
        for(int i=k+1; i<=n; i++){
            if(same[i]==same[i-k] && same[i]!=0){
                fl=0;
            }
            if(same[i]!=same[i-k]){
                if(same[i]>same[i-k])b[i]=1;
                else b[i]=0;
                for(int j=i-k; j>=1 && b[j]==-1; j-=k){
                    b[j]=b[j+k]-same[j+k];
                }
            }

        }
        ll c=0;
        for(int i=1; i<=k; i++){
            if(b[i]==1)a[1]--;
            if(b[i]==-1)c++;
        }
        if(!fl || a[1]<0){
            cout<<0<<endl;
        }
        else{
            cout<<cnt(a[1], c)<<endl;
        }




    }

    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