oj.uz

Submission #883836

# Submission time Handle Problem Language Result Execution time Memory
883836 2023-12-06T07:41:57 Z noiaint Binaria (CCO23_day1problem1) C++17
0 / 25
 12 ms 12892 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e6 + 3; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, k;
int a[N];

int pw(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1LL * res * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return res;
}

int fac[N], inv[N];
void pre() {
    int n = 1e6;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1LL * fac[i - 1] * i % mod;
    inv[n] = pw(fac[n], mod - 2);
    for (int i = n; i >= 1; --i) inv[i - 1] = 1LL * inv[i] * i % mod;
}
int nCk(int n, int k) {
    if (k < 0 || k > n) return 0;
    return 1LL * fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int ok[N];

void process() {
    pre();

    cin >> n >> k;
    for (int i = 1; i <= n - k + 1; ++i) cin >> a[i];

    memset(ok, -1, sizeof ok);

    for (int i = 1; i <= n - k; ++i) {
        if (a[i] == a[i + 1]) ok[i] = ok[i + k];

        if (a[i] < a[i + 1]) {
            ok[i] = 0;
            if (ok[i + k] == 0) {
                cout << 0;
                return;
            }
        }

        if (a[i] > a[i + 1]) {
            ok[i] = 1;
            if (ok[i + k] == 1) {
                cout << 0;
                return;
            }
        }

        if (abs(a[i] - a[i + 1]) > 1) {
            cout << 0;
            return;
        }
    }

    int cnt = 0;
    for (int i = 1; i <= k; ++i) {
        a[1] -= (ok[i] == 1);
        cnt += (ok[i] == -1);
    }

    debug(cnt, a[1]);

    cout << nCk(cnt, a[1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #else
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;

    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

Compilation message

Main.cpp: In function 'void process()':
Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
Main.cpp:112:5: note: in expansion of macro 'debug'
  112 |     debug(cnt, a[1]);
      |     ^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 12 ms 12888 KB Output is correct
3 Correct 11 ms 12892 KB Output is correct
4 Correct 11 ms 12772 KB Output is correct
5 Correct 11 ms 12888 KB Output is correct
6 Incorrect 11 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 12 ms 12888 KB Output is correct
3 Correct 11 ms 12892 KB Output is correct
4 Correct 11 ms 12772 KB Output is correct
5 Correct 11 ms 12888 KB Output is correct
6 Incorrect 11 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 12 ms 12888 KB Output is correct
3 Correct 11 ms 12892 KB Output is correct
4 Correct 11 ms 12772 KB Output is correct
5 Correct 11 ms 12888 KB Output is correct
6 Incorrect 11 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 12 ms 12888 KB Output is correct
3 Correct 11 ms 12892 KB Output is correct
4 Correct 11 ms 12772 KB Output is correct
5 Correct 11 ms 12888 KB Output is correct
6 Incorrect 11 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 12 ms 12888 KB Output is correct
3 Correct 11 ms 12892 KB Output is correct
4 Correct 11 ms 12772 KB Output is correct
5 Correct 11 ms 12888 KB Output is correct
6 Incorrect 11 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12888 KB Output is correct
2 Correct 12 ms 12888 KB Output is correct
3 Correct 11 ms 12892 KB Output is correct
4 Correct 11 ms 12772 KB Output is correct
5 Correct 11 ms 12888 KB Output is correct
6 Incorrect 11 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -