제출 #1125683

#제출 시각아이디문제언어결과실행 시간메모리
1125683tintingyn21Binaria (CCO23_day1problem1)C++20
0 / 25
20 ms16712 KiB
// author : daohuyenchi #ifdef LOCAL #include "D:\C++ Submit\debug.h" #else #define debug(...) #endif #include <bits/stdc++.h> using namespace std; #define ull unsigned long long #define db double #define i32 int32_t #define i64 int64_t #define ll long long // #define fi first #define se second // #define int long long // consider carefully // #define pii pair <int, int> #define pll pair <ll, ll> #define PAIR make_pair #define TUP make_tuple // TIME IS LIMITED ... #define rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define repd(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define repv(v, H) for(auto &v: H) // REFLECT ON THE PAST ... #define RESET(c, x) memset(c, x, sizeof(c)) #define MASK(i) (1LL << (i)) #define BIT(mask, i) (((mask) >> (i)) & 1LL) #define ONBIT(mask, i) ((mask) | (1LL << (i))) #define OFFBIT(mask, i) ((mask) &~ (1LL << (i))) #define COUNTBIT __builtin_popcountll // 30 / 1 / 2024 ? love is zero... start from zero #define vi vector <int> #define vll vector <ll> #define Lower lower_bound #define Upper upper_bound #define all(v) (v).begin(), (v).end() #define special(H) (H).resize(distance(H.begin(), unique(all(H)))) // #define sp ' ' #define nl '\n' #define EL { cerr << '\n'; } #define yes "YES" #define no "NO" #define Log2(n) (63 - __builtin_clzll(n)) #define left __left__ #define right __right__ #define lps(id) ((id) << 1) #define rps(id) ((id) << 1 | 1) //____________________________________________________________________ template <class X, class Y> bool maximize(X &a, const Y &b) { if(a < b) return a = b, true; else return false; } template <class X, class Y> bool minimize(X &a, const Y &b) { if(a > b) return a = b, true; else return false; } template <class... T> void print(T&&... n) { using exp = int[]; exp{ 0, (cerr << n << sp, 0)... }; cerr << nl; } template <class T, class... C> void assign(int n, T v, C&&... a) { using e = int[]; e { (a.assign(n, v), 0)...}; } template <class... C> void resize(int n, C&&... a) { using e = int[]; e { (a.resize(n), 0)...}; } template <class T> using vector2d = vector<vector<T>>; template <class T> using vector3d = vector<vector2d<T>>; template <class T> int ssize(T &a) { return (int) a.size(); } //____________________________________________________________________ mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); const long long MOD = 1e6 + 3; // const int MOD[2] = {1000000009, 998244353}; template<class X> void modmize(X &x, long long cur_Mod = MOD) { if(x >= cur_Mod) x -= cur_Mod; if(x < 0) x += cur_Mod; } int mod_plus(int A, int B) { modmize(A += B); return A; } const long long oo = 1e18 + 7; const long long LINF = 1e18 + 7; const int IINF = 2e9; const int nmax = 2e5 + 10; const int MAX = 1e6; const int base = 311; const double eps = 1e-6; const int block = 500; static const double PI = acos(-1.0); //____________________________________________________________________ int n, k; int x[nmax], a[nmax]; struct DSU { vector<int> parent; void Init(int _n) { parent.assign(_n + 1, -1); return; } void Reset(int _n = 0) { for (int i = 1; i <= _n; ++i) { parent[i] = -1; } } int Find(int u) { return (parent[u] < 0 ? u : parent[u] = Find(parent[u])); } int Son(int u) { u = Find(u); return - parent[u]; } bool Merge(int u, int v) { u = Find(u); v = Find(v); if(u == v) return false; if(parent[u] > parent[v]) swap(u, v); parent[u] += parent[v]; parent[v] = u; return true; } } dsu; int64_t Pow(ll a, ll b) { ll cur = 1; for(; b > 0; b >>= 1) { if(b & 1LL) cur = cur * a % MOD; a = a * a % MOD; } return cur; } struct combinatorics { vector<ll> fac, ifac; void init(int _n) { fac.assign(_n + 5, 0); ifac.assign(_n + 5, 0); fac[0] = 1; for (int i = 1; i <= _n; ++i) { fac[i] = fac[i - 1] * i % MOD; } ifac[_n] = Pow(fac[_n], MOD - 2); for (int i = _n - 1; i >= 0; --i) { ifac[i] = ifac[i + 1] * (i + 1) % MOD; } } // n choose k ll ncr(int n, int k) { if (k > n) return 0; if (k == 0 && n == 0) return 1; if (k == 0) return 1; if (n == 0) return 0; return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; } // n permutation k ll npr(int n, int k) { if (k > n) return 0; return fac[n] * ifac[n - k] % MOD; } // (k, n) = 0 if k > n // (k, n) = n * nf[k] * (k - 1, n - 1) // sigma (i, n) = 2 ^ n :i = 0 -> n // sigma (k, i) = (k + 1, n + 1) :i = 0 -> n // sigma (i, n + i) = (m, n + m + 1) :i = 0 -> m // sigma {(i, n) ^ 2} = (n, 2n) :i = 0 -> n // sigma {k * (k, n)} = n * 2 ^ (n - 1) :i = 1 -> n // x[1] + x[2] + .. + x[n] = m (x[i] >= 0) => (n - 1, m + n - 1) // x[1] + x[2] + .. + x[n] <= m (x[i] >= 0) => (n, m + n) // cell(u, v) -> cell(x, y) => (x - u, x + y - u - v) // choose len elements in n elements (not need to be diifer) = ncr(n - 1 + len, len) // the number of regular bracket strings of length 2⋅n is equal to (1 / (n + 1)) * ncr(2 * n, n) } C; void tintingyn() { cin >> n >> k; rep (i, k, n) { cin >> x[i]; } C.init(1e6); dsu.Init(n); memset(a, -1, sizeof a); rep (i, n - k + 1, n - 1) { if (x[i] != x[i + 1]) { if (abs(x[i] - x[i + 1]) > 1) { cout << 0 << nl; exit(0); } if (x[i + 1] > x[i]) a[i + 1] = 1, a[i - k + 1] = 0; else a[i + 1] = 0, a[i - k + 1] = 1; } else { dsu.Merge(i + 1, i - k + 1); } } vector2d < int > List; assign(n + 2, vector < int > (), List); rep (i, 1, n) { List[dsu.Find(i)].push_back(i); } rep (i, 1, n) { if (dsu.Find(i) == i) { int ok = -1; repv (v, List[i]) { if (ok == -1) { if (a[v] != -1) ok = a[v]; } else { if (ok != a[v]) { cout << 0 << nl; exit(0); } } } if (ok != -1) { repv (v, List[i]) { a[v] = ok; } } else { } } } int cnt = 0; int sum = x[k]; vector < bool > vis(n + 2, 0); rep (i, 1, k) { int p = dsu.Find(i); if (a[p] != -1) sum -= a[p]; else cnt++; vis[p] = 1; } ll ans = C.ncr(cnt, sum); // rep (i, k + 1, n) { // int p = dsu.Find(i); // if (vis[p] == 0) { // vis[p] = 1; // ans = ans * Pow(2, dsu.Son(p)) % MOD; // } // } cout << ans << nl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //________________________________________________________________ #define TASK "2" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } //________________________________________________________________ // CODE FROM HERE ...! int num_test = 1; // cin >> num_test; while(num_test--) { tintingyn(); } cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" << nl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:312:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  312 |     { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:312:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  312 |     { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...