Submission #1027242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027242		nathan4690	Binaria (CCO23_day1problem1)	C++17	25 / 25	71 ms	29776 KiB

Main

// CCO '23 P1 - Binaria
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18, mod=1e6+3;

ll n, k, a[maxn], l, r, ans;
char res[maxn];

ll fac[maxn], inv[maxn];

ll powmod(ll base, ll exp){
    if(exp == 0) return 1ll;
    if(exp == 1) return base % mod;
    ll v = powmod(base, exp/2);
    if(exp % 2) return v*v%mod*base%mod;
    else return v*v%mod;
}

void preprocess(){
    fac[0] = 1;
    f1(i,n) fac[i] = fac[i-1] * i % mod;
    inv[n] = powmod(fac[n], mod-2);
    inv[0] = 1;
    for(ll i=n-1;i>=1;i--){
        inv[i] = (inv[i+1] * (i+1)) % mod;
    }
}

ll C(ll n, ll k){
    if(k > n || k < 0) return 0ll;
    return fac[n] * inv[k] % mod * inv[n-k] % mod;
}

void solve(){
    // 0: character is 0
    // 1: character is 1
    // x: character is based on the (i-k)th character
    // ?: unknown
    f1(i,n) res[i] = '?';
    f1(i,n-k){
        l = i; r = i + k;
        if(abs(a[i+1] - a[i]) > 1){
            cout << 0;el;
            return;
        }
        if(a[i+1] > a[i]){
            res[r] = '1';
            ll idx = l;
            bool flag = false;
            while(res[idx] == 'x'){
                res[idx] = char('0' + (ll)flag);
                flag = !flag;
                idx = idx - k;
                // if(idx <= 0) break;
            }
            if((res[idx] == '1' && (!flag)) || (res[idx] == '0' && flag)){
                cout << 0;el;
                return;
            }
            res[idx] = char('0' + (ll)flag);
        }else if(a[i+1] == a[i]){
            if(res[l] == '?') res[r] = 'x';
            else res[r] = res[l];
        }else{
            res[r] = '0';
            ll idx = l;
            bool flag = true;
            while(res[idx] == 'x'){
                res[idx] = char('0' + (ll)flag);
                // flag = !flag;
                idx = idx - k;
                // if(idx <= 0) break;
            }
            if((res[idx] == '1' && (!flag)) || (res[idx] == '0' && flag)){
                cout << 0;el;
                return;
            }
            res[idx] = char('0' + (ll)flag);
        }
    }
    // f1(i,n) cout << res[i] << ' ';el;
    ll ccnt = 0;
    for(ll i=n-k+1;i<=n;i++){
        ccnt += (!(res[i] == '0' || res[i] == '1'));
        if(res[i] == '1') a[n-k+1]--;
    }
    // cout << ccnt << ' ' << a[n-k+1];el;
    cout << C(ccnt, a[n-k+1]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> k;
    preprocess();
    f1(i,n - k + 1) cin >> a[i];
    solve();
    return 0;
}

/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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