Submission #967947

#	Time	Username	Problem	Language	Result	Execution time	Memory
967947		Pring	Binaria (CCO23_day1problem1)	C++17	25 / 25	63 ms	4484 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 1000005, mod = 1000003;
int n, k;
int a[MXN], cand, lst;

ll POW(ll a, ll b) {
    ll ans = 1;
    for (int i = 1 << 30; i > 0; i >>= 1) {
        ans = ans * ans % mod;
        if (i & b) ans = ans * a % mod;
    }
    return ans;
}

int C(int n, int k) {
    if (n < k) return 0;
    ll up = 1, dn = 1;
    FOR(i, 1, n + 1) up = up * i % mod;
    FOR(i, 1, k + 1) dn = dn * i % mod;
    FOR(i ,1, (n - k) + 1) dn = dn * i % mod;
    return up * POW(dn, mod - 2) % mod;
}

int GROUP(int x) {
    int y = 0, fff = 0;
    for (int i = x; i + 1 < n - k + 1; i += k) {
        if (a[i] == a[i + 1]) continue;
        int z = (a[i] < a[i + 1] ? 1 : -1);
        if (fff == 0) fff = z;
        if (y == z) return 0;
        y = z;
    }
    if (fff == 1) {
        cand--;
    } else if (fff == -1) {
        cand--;
        lst--;
    }
    return 1;
}

void miku() {
    cin >> n >> k;
    FOR(i, 0, n - k + 1) cin >> a[i];
    ll ans = 1;
    lst = a[0];
    cand = k;
    FOR(i, 1, n - k + 1) if (abs(a[i] - a[i - 1]) > 1) {
        cout << 0 << '\n';
        return;
    }
    FOR(i, 0, k) {
        ans = ans * GROUP(i) % mod;
        debug(cand, lst);
    }
    cout << ans * C(cand, lst) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void miku()':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:73:9: note: in expansion of macro 'debug'
   73 |         debug(cand, lst);
      |         ^~~~~

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