Submission #1113058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113058		duckindog	Binaria (CCO23_day1problem1)	C++17	25 / 25	91 ms	32756 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2'000'000 + 10,
          M = 1'000'003;
int n, k;
int a[N];

int id[N];
int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
void add(int u, int v) {
  u = root(u); v = root(v);
  if (u == v) return;
  if (id[u] > id[v]) swap(u, v);
  id[u] += id[v];
  id[v] = u;
}

int idx[N][2];

int powder(int a, int b) { 
  int ret = 1;
  for (; b; b /= 2, a = 1ll * a * a % M) { 
    if (b & 1) ret = 1ll * ret * a % M;
  }
  return ret;
}

int fac[N], ifac[N];
void init() { 
  const int SZ = 1'000'000;
  fac[0] = 1;
  for (int i = 1; i <= SZ; ++i) fac[i] = 1ll * fac[i - 1] * i % M;
  
  ifac[SZ] = powder(fac[SZ], M - 2);
  for (int i = SZ; i >= 1; --i) ifac[i - 1] = 1ll * ifac[i] * i % M;
}
inline int C(int n, int k) { return 1ll * fac[n] * ifac[n - k] % M * ifac[k] % M; }

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

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

  int possible = 0, impossible = 1;
  for (int i = 1; i <= n; ++i) idx[i][0] = 2 * i, idx[i][1] = 2 * i + 1;
  
  memset(id, -1, sizeof id);
  for (int i = k + 1; i <= n; ++i) { 
    if (a[i] - a[i - 1] == 1) { 
      add(idx[i][1], possible);
      add(idx[i - k][0], possible);

      add(idx[i][0], impossible);
      add(idx[i - k][1], impossible);
    }
    
    if (a[i] - a[i - 1] == -1) { 
      add(idx[i][0], possible);
      add(idx[i - k][1], possible);
      
      add(idx[i][1], impossible);
      add(idx[i - k][0], impossible);
    }

    if (a[i] - a[i - 1] == 0) { 
      add(idx[i][0], idx[i - k][0]);
      add(idx[i][1], idx[i - k][1]);
    }
  }

  for (int i = 1; i <= n; ++i)
    if (root(idx[i][0]) == root(idx[i][1])) { cout << 0 << "\n"; return 0; }
  
  int sum = a[k], cnt = 0;
  for (int i = 1; i <= k; ++i) { 
    if (root(idx[i][1]) == root(possible)) sum -= 1;
    else if (root(idx[i][0]) != root(possible)) cnt += 1;
  }
  
  init();
  cout << C(cnt, sum) << "\n";
}

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