Submission #932849

#	Time	Username	Problem	Language	Result	Execution time	Memory
932849		Son	Binaria (CCO23_day1problem1)	C++14	25 / 25	304 ms	21052 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define fi first
#define se second
#define mp make_pair

int n,k;
int A[1000005];
int fact[1000005], inv[1000005];
int mo = 1e6 + 3;
int B[1000005];

int expo( int a, int b ){
    if ( b == 0 ) return 1;
    int half = expo(a,b/2);
    half = ( 1LL * half * half ) % mo;
    if ( b & 1 ){
        half = ( 1LL * half * a ) % mo;
    }
    return half;
}

int C( int N, int K ){
    if ( K > N || K < 0 ) return 0;
    int ans = (fact[N] * 1LL * inv[K]) % mo;
    ans = ( ans * 1LL * inv[N-K] ) % mo;
    return ans; 
}

void fail(){
    printf("0\n");
    exit(0);
}

int main(){
    
    scanf("%d%d",&n,&k);
    for ( int i = 1; i <= n-k+1; i++ ){
        scanf("%d",&A[i]);
    }

    fact[0] = inv[0] = 1;
    for ( int i = 1; i <= n; i++ ){
        fact[i] = ( fact[i-1] * 1LL * i ) % mo;
        inv[i] = expo(fact[i], mo - 2) % mo;
        B[i] = 2;
    }

    for ( int i = n-k; i >= 1; i-- ){
        if ( abs(A[i] - A[i+1]) > 1 ){
            fail();
        }
        if ( A[i] > A[i+1] ){
            if ( B[i+k] == 1 ){
                fail();
            }
            B[i] = 1;
        } else if ( A[i] < A[i+1] ){
            if ( B[i+k] == 0 ){
                fail();
            }
            B[i] = 0;
        } else {
            B[i] = B[i+k];
        }
    }    
    
    int N = 0, K = A[1];
    for ( int i = 1; i <= k; i++ ){
        if ( B[i] == 1 ){
            K--;
        } 
        if ( B[i] == 2 ){
            N++;
        }
    }
    printf("%d\n",C(N,K));
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d",&A[i]);
      |         ~~~~~^~~~~~~~~~~~

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