Submission #1177557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177557		Zero_OP	Binaria (CCO23_day1problem1)	C++20	25 / 25	48 ms	12104 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

// #define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

const int MAX = 1e6 + 5;
const int mod = 1e6 + 3;

int N, K, A[MAX], lab[MAX], decision[MAX];

int root(int u){
      return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}

bool join(int u, int v){
      u = root(u); v = root(v);
      if(u == v) return false;
      if(lab[u] > lab[v]) swap(u, v);
      lab[u] += lab[v];
      lab[v] = u;
      return true;
}

int binpow(int a, int n){
      int result = 1;
      for(; n > 0; n >>= 1, a = 1LL * a * a % mod){
            if(n & 1) result = 1LL * result * a % mod;
      }
      return result;
}

int C(int n, int k){
      assert(n >= k);
      int result = 1, inv = 1;
      for(int i = 0; i < k; ++i){
            inv = 1LL * inv * (i + 1) % mod;
            result = 1LL * result * (n - i) % mod;
      }    
      result = 1LL * result * binpow(inv, mod - 2) % mod;
      return result;
}

int main(){
      ios_base::sync_with_stdio(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif //LOCAL

      cin >> N >> K;
      for(int i = 0; i < N - K + 1; ++i) cin >> A[i];

      for(int i = 0; i < N; ++i){
            decision[i] = -1;
            lab[i] = -1;
      }

      for(int i = 0; i < N - K; ++i){
            if(A[i] == A[i+1] + 1){
                  decision[root(i)] = 1;
                  decision[root(i + K)] = 0;
            } else if(A[i] == A[i+1] - 1){
                  decision[root(i)] = 0;
                  decision[root(i+K)] = 1;
            } else if(A[i] == A[i+1]){
                  join(i, i+K);
            } else assert(false);
      }

      int unknown = 0, ones = A[0];
      for(int i = 0; i < K; ++i){
            if(decision[root(i)] == 1) --ones;
            else if(decision[root(i)] == -1) ++unknown; 
      }

      cout << C(unknown, ones) << '\n';

      return 0;
}

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