Submission #1044907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044907		PagodePaiva	Binaria (CCO23_day1problem1)	C++17	25 / 25	157 ms	28848 KiB

Main

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6+10;
int pai[N];
int res[N];
const int mod = 1e6 + 3;

int binpow(int a, int b, int m){
    if(b == 0) return 1;
    int t = binpow(a, b/2, m);
    if(b % 2 == 0) return (t*t) % m;
    return (((t*t) % m )*a) % m;
}

int fat(int x){
    if(x < 0) return 0;
    if(x == 0) return 1;
    return (fat(x-1)*x) % mod;
}

int choose(int a, int b){
    swap(a, b);
    return ((fat(a) % mod)*binpow((fat(b)*fat(a-b)) % mod, mod-2, mod)) % mod;
}

int32_t main(){
    int n, k;
    cin >> n >> k;
    vector <int> v;
    for(int i = 1;i <= n-k+1;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    for(int i = 1;i < v.size();i++){
        pai[i] = v[i]-v[i-1];
        //cout << pai[i] << ' ';
    }
    // cout << '\n';
    int cnt = 0;
    int val = v[0];
    for(int i = 1;i <= k;i++){
        int at = i;
        res[i] = -1;
        while(at < n){
            if(pai[at] == 0){
                at += k;
            }
            else{
                if(pai[at] == -1){
                    res[i] = 1;
                    break;
                }
                else{
                    res[i] = 0;
                    break;
                }
            }
        }
        if(res[i] == -1) cnt++;
        else val -= res[i];
    }
    // cout << val << endl;
    if(val < 0){
        cout << 0 << endl;
        return 0;
    }
    int resposta = choose(val, cnt);
    for(int i = 1;i <= k;i++){
        if(res[i] == -1 and val > 0){
            val--;
            res[i] = 1;
        }
        else if(val == 0 and res[i] == -1) res[i] = 0;
    }

    int pref = 0;
    for(int i = 1;i <= k;i++){
        pref += res[i];
       // cout << res[i] << ' ';
    } 
    if(pref != v[0]){
        cout << 0 << endl;
        return 0;
    }
    for(int i = k+1;i <= n;i++){
        res[i] = v[i-k] - (pref-res[i-k]);
        pref -= res[i-k];
        pref += res[i];
        if(res[i] != 0 and res[i] != 1){
            cout << 0 << endl;
            return 0;
        }
    }
    cout << resposta << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:38:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 1;i < v.size();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