답안 #795780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795780	2023-07-27T14:49:05 Z	marvinthang	Binaria (CCO23_day1problem1)	C++17	25 / 25	68 ms	12060 KB

Main

/*************************************
*    author: marvinthang             *
*    created: 21.07.2023 08:49:51    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

const int MOD = 1e6 + 3;
namespace Mod {

    inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
        unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
    #ifdef __GNUC__
        asm(
            "divl %4 \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (y)
        );
    #else
        __asm {
            mov edx, dword ptr[xh];
            mov eax, dword ptr[xl];
            div dword ptr[y];
            mov dword ptr[d], eax;
            mov dword ptr[m], edx;
        };
    #endif
        out_d = d; out_m = m;
    }

    template <class T> T invGeneral(T a, T b) {
        a %= b;
        if (!a) return b == 1 ? 0 : -1;
        T x = invGeneral(b, a);
        return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
    }

    template <int MOD>
    struct ModInt {
        
        unsigned int val;

        ModInt(void): val(0) {}
        ModInt(const long long &x) { *this = x; }

        ModInt & normalize(const unsigned int &v) {
            val = v >= MOD ? v - MOD : v;
            return *this;
        }

        bool operator ! (void) { return !val; }

        ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
        ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }

        ModInt operator - (void) { return ModInt(MOD - val); }

        ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
        ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
        ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }

        ModInt & operator *= (const ModInt &other) {
            unsigned dummy;
            fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
            return *this;
        }

        ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
        ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
        ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
        ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }

        ModInt pow(long long n) const {
            assert(n >= 0);
            ModInt res = 1, a = *this;
            for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
            return res;
        }

        ModInt inv(void) const {
            int i = invGeneral((int) val, MOD);
            assert(~i);
            return i;
        }

        ModInt & operator ++ (void) { return *this += 1; }
        ModInt & operator -- (void) { return *this -= 1; }
        ModInt operator ++ (int) { ModInt old = *this; operator ++(); return old; }
        ModInt operator -- (int) { ModInt old = *this; operator --(); return old; }

        friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
        friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
        friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
        friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
        friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
        friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }

        bool operator < (const ModInt &other) const { return val < other.val; }
        bool operator > (const ModInt &other) const { return val > other.val; }
        bool operator <= (const ModInt &other) const { return val <= other.val; }
        bool operator >= (const ModInt &other) const { return val >= other.val; }
        bool operator == (const ModInt &other) const { return val == other.val; }
        bool operator != (const ModInt &other) const { return val != other.val; }
        explicit operator bool(void) const { return val; }
        explicit operator int(void) const { return val; }

    };  

    using Modular = ModInt <MOD>;

}

using namespace Mod;

// end of template

const int MAX = 1e6 + 6;

int N, K, A[MAX];

void init(void) {
	cin >> N >> K;
	REP(i, N - K + 1) cin >> A[i];
}

int lab[MAX], colors[MAX];

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

bool join(int u, int v) {
	if ((u = find(u)) == (v = find(v))) return false;
	if (lab[u] > lab[v]) swap(u, v);
	lab[u] += lab[v];
	lab[v] = u;
	if (colors[v] != -1) colors[u] = colors[v];
	return true;
}

void process(void) {
	memset(lab, -1, sizeof(lab));
	memset(colors, -1, sizeof(colors));
	REP(i, N - K) {
		if (A[i] > A[i + 1]) {
			colors[find(i)] = 1;
			colors[find(i + K)] = 0;
		} else if (A[i] < A[i + 1]) {
			colors[find(i)] = 0;
			colors[find(i + K)] = 1;
		} else join(i, i + K);
	}
	int cnt = 0;
	REP(i, K) {
		int c = colors[find(i)];
		if (c != -1) A[0] -= c;
		else ++cnt;
	}
	Modular a = 1, b = 1;
	REP(i, A[0]) {
		a *= cnt - i;
		b *= i + 1;
	}
	cout << a / b << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("cco23p1");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:204:2: note: in expansion of macro 'file'
  204 |  file("cco23p1");
      |  ^~~~
Main.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:204:2: note: in expansion of macro 'file'
  204 |  file("cco23p1");
      |  ^~~~

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8148 KB	Output is correct
2	Correct	3 ms	8148 KB	Output is correct
3	Correct	3 ms	8148 KB	Output is correct
4	Correct	4 ms	8148 KB	Output is correct
5	Correct	3 ms	8148 KB	Output is correct
6	Correct	3 ms	8148 KB	Output is correct
7	Correct	3 ms	8148 KB	Output is correct
8	Correct	3 ms	8148 KB	Output is correct
9	Correct	3 ms	8148 KB	Output is correct
10	Correct	3 ms	8148 KB	Output is correct
11	Correct	4 ms	8148 KB	Output is correct
12	Correct	3 ms	8148 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8148 KB	Output is correct
2	Correct	3 ms	8148 KB	Output is correct
3	Correct	3 ms	8148 KB	Output is correct
4	Correct	4 ms	8148 KB	Output is correct
5	Correct	3 ms	8148 KB	Output is correct
6	Correct	3 ms	8148 KB	Output is correct
7	Correct	3 ms	8148 KB	Output is correct
8	Correct	3 ms	8148 KB	Output is correct
9	Correct	3 ms	8148 KB	Output is correct
10	Correct	3 ms	8148 KB	Output is correct
11	Correct	4 ms	8148 KB	Output is correct
12	Correct	3 ms	8148 KB	Output is correct
13	Correct	3 ms	8148 KB	Output is correct
14	Correct	3 ms	8148 KB	Output is correct
15	Correct	3 ms	8148 KB	Output is correct
16	Correct	3 ms	8148 KB	Output is correct
17	Correct	3 ms	8148 KB	Output is correct
18	Correct	3 ms	8148 KB	Output is correct
19	Correct	3 ms	8148 KB	Output is correct
20	Correct	3 ms	8148 KB	Output is correct
21	Correct	3 ms	8148 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8148 KB	Output is correct
2	Correct	3 ms	8148 KB	Output is correct
3	Correct	3 ms	8148 KB	Output is correct
4	Correct	4 ms	8148 KB	Output is correct
5	Correct	3 ms	8148 KB	Output is correct
6	Correct	3 ms	8148 KB	Output is correct
7	Correct	3 ms	8148 KB	Output is correct
8	Correct	3 ms	8148 KB	Output is correct
9	Correct	3 ms	8148 KB	Output is correct
10	Correct	3 ms	8148 KB	Output is correct
11	Correct	4 ms	8148 KB	Output is correct
12	Correct	3 ms	8148 KB	Output is correct
13	Correct	3 ms	8148 KB	Output is correct
14	Correct	3 ms	8148 KB	Output is correct
15	Correct	3 ms	8148 KB	Output is correct
16	Correct	3 ms	8148 KB	Output is correct
17	Correct	3 ms	8148 KB	Output is correct
18	Correct	3 ms	8148 KB	Output is correct
19	Correct	3 ms	8148 KB	Output is correct
20	Correct	3 ms	8148 KB	Output is correct
21	Correct	3 ms	8148 KB	Output is correct
22	Correct	4 ms	8148 KB	Output is correct
23	Correct	4 ms	8148 KB	Output is correct
24	Correct	3 ms	8148 KB	Output is correct
25	Correct	3 ms	8148 KB	Output is correct
26	Correct	3 ms	8148 KB	Output is correct
27	Correct	3 ms	8148 KB	Output is correct
28	Correct	3 ms	8148 KB	Output is correct
29	Correct	3 ms	8148 KB	Output is correct
30	Correct	3 ms	8148 KB	Output is correct
31	Correct	3 ms	8148 KB	Output is correct
32	Correct	3 ms	8148 KB	Output is correct
33	Correct	3 ms	8148 KB	Output is correct
34	Correct	4 ms	8076 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8148 KB	Output is correct
2	Correct	3 ms	8148 KB	Output is correct
3	Correct	3 ms	8148 KB	Output is correct
4	Correct	4 ms	8148 KB	Output is correct
5	Correct	3 ms	8148 KB	Output is correct
6	Correct	3 ms	8148 KB	Output is correct
7	Correct	3 ms	8148 KB	Output is correct
8	Correct	3 ms	8148 KB	Output is correct
9	Correct	3 ms	8148 KB	Output is correct
10	Correct	3 ms	8148 KB	Output is correct
11	Correct	4 ms	8148 KB	Output is correct
12	Correct	3 ms	8148 KB	Output is correct
13	Correct	3 ms	8148 KB	Output is correct
14	Correct	3 ms	8148 KB	Output is correct
15	Correct	3 ms	8148 KB	Output is correct
16	Correct	3 ms	8148 KB	Output is correct
17	Correct	3 ms	8148 KB	Output is correct
18	Correct	3 ms	8148 KB	Output is correct
19	Correct	3 ms	8148 KB	Output is correct
20	Correct	3 ms	8148 KB	Output is correct
21	Correct	3 ms	8148 KB	Output is correct
22	Correct	4 ms	8148 KB	Output is correct
23	Correct	4 ms	8148 KB	Output is correct
24	Correct	3 ms	8148 KB	Output is correct
25	Correct	3 ms	8148 KB	Output is correct
26	Correct	3 ms	8148 KB	Output is correct
27	Correct	3 ms	8148 KB	Output is correct
28	Correct	3 ms	8148 KB	Output is correct
29	Correct	3 ms	8148 KB	Output is correct
30	Correct	3 ms	8148 KB	Output is correct
31	Correct	3 ms	8148 KB	Output is correct
32	Correct	3 ms	8148 KB	Output is correct
33	Correct	3 ms	8148 KB	Output is correct
34	Correct	4 ms	8076 KB	Output is correct
35	Correct	55 ms	11988 KB	Output is correct
36	Correct	52 ms	12000 KB	Output is correct
37	Correct	52 ms	12044 KB	Output is correct
38	Correct	52 ms	12020 KB	Output is correct
39	Correct	48 ms	12008 KB	Output is correct
40	Correct	49 ms	11940 KB	Output is correct
41	Correct	51 ms	11984 KB	Output is correct
42	Correct	49 ms	12000 KB	Output is correct
43	Correct	46 ms	11960 KB	Output is correct
44	Correct	58 ms	12012 KB	Output is correct
45	Correct	47 ms	11976 KB	Output is correct
46	Correct	45 ms	12044 KB	Output is correct
47	Correct	49 ms	12012 KB	Output is correct
48	Correct	50 ms	12004 KB	Output is correct
49	Correct	50 ms	11980 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8148 KB	Output is correct
2	Correct	3 ms	8148 KB	Output is correct
3	Correct	3 ms	8148 KB	Output is correct
4	Correct	4 ms	8148 KB	Output is correct
5	Correct	3 ms	8148 KB	Output is correct
6	Correct	3 ms	8148 KB	Output is correct
7	Correct	3 ms	8148 KB	Output is correct
8	Correct	3 ms	8148 KB	Output is correct
9	Correct	3 ms	8148 KB	Output is correct
10	Correct	3 ms	8148 KB	Output is correct
11	Correct	4 ms	8148 KB	Output is correct
12	Correct	3 ms	8148 KB	Output is correct
13	Correct	3 ms	8148 KB	Output is correct
14	Correct	3 ms	8148 KB	Output is correct
15	Correct	3 ms	8148 KB	Output is correct
16	Correct	3 ms	8148 KB	Output is correct
17	Correct	3 ms	8148 KB	Output is correct
18	Correct	3 ms	8148 KB	Output is correct
19	Correct	3 ms	8148 KB	Output is correct
20	Correct	3 ms	8148 KB	Output is correct
21	Correct	3 ms	8148 KB	Output is correct
22	Correct	4 ms	8148 KB	Output is correct
23	Correct	4 ms	8148 KB	Output is correct
24	Correct	3 ms	8148 KB	Output is correct
25	Correct	3 ms	8148 KB	Output is correct
26	Correct	3 ms	8148 KB	Output is correct
27	Correct	3 ms	8148 KB	Output is correct
28	Correct	3 ms	8148 KB	Output is correct
29	Correct	3 ms	8148 KB	Output is correct
30	Correct	3 ms	8148 KB	Output is correct
31	Correct	3 ms	8148 KB	Output is correct
32	Correct	3 ms	8148 KB	Output is correct
33	Correct	3 ms	8148 KB	Output is correct
34	Correct	4 ms	8076 KB	Output is correct
35	Correct	55 ms	11988 KB	Output is correct
36	Correct	52 ms	12000 KB	Output is correct
37	Correct	52 ms	12044 KB	Output is correct
38	Correct	52 ms	12020 KB	Output is correct
39	Correct	48 ms	12008 KB	Output is correct
40	Correct	49 ms	11940 KB	Output is correct
41	Correct	51 ms	11984 KB	Output is correct
42	Correct	49 ms	12000 KB	Output is correct
43	Correct	46 ms	11960 KB	Output is correct
44	Correct	58 ms	12012 KB	Output is correct
45	Correct	47 ms	11976 KB	Output is correct
46	Correct	45 ms	12044 KB	Output is correct
47	Correct	49 ms	12012 KB	Output is correct
48	Correct	50 ms	12004 KB	Output is correct
49	Correct	50 ms	11980 KB	Output is correct
50	Correct	60 ms	11976 KB	Output is correct
51	Correct	68 ms	12040 KB	Output is correct
52	Correct	68 ms	12060 KB	Output is correct
53	Correct	65 ms	11960 KB	Output is correct
54	Correct	62 ms	11980 KB	Output is correct
55	Correct	65 ms	11928 KB	Output is correct
56	Correct	61 ms	11928 KB	Output is correct
57	Correct	58 ms	12016 KB	Output is correct
58	Correct	60 ms	12060 KB	Output is correct
59	Correct	63 ms	12024 KB	Output is correct
60	Correct	56 ms	12000 KB	Output is correct

Subtask #6
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8148 KB	Output is correct
2	Correct	3 ms	8148 KB	Output is correct
3	Correct	3 ms	8148 KB	Output is correct
4	Correct	4 ms	8148 KB	Output is correct
5	Correct	3 ms	8148 KB	Output is correct
6	Correct	3 ms	8148 KB	Output is correct
7	Correct	3 ms	8148 KB	Output is correct
8	Correct	3 ms	8148 KB	Output is correct
9	Correct	3 ms	8148 KB	Output is correct
10	Correct	3 ms	8148 KB	Output is correct
11	Correct	4 ms	8148 KB	Output is correct
12	Correct	3 ms	8148 KB	Output is correct
13	Correct	3 ms	8148 KB	Output is correct
14	Correct	3 ms	8148 KB	Output is correct
15	Correct	3 ms	8148 KB	Output is correct
16	Correct	3 ms	8148 KB	Output is correct
17	Correct	3 ms	8148 KB	Output is correct
18	Correct	3 ms	8148 KB	Output is correct
19	Correct	3 ms	8148 KB	Output is correct
20	Correct	3 ms	8148 KB	Output is correct
21	Correct	3 ms	8148 KB	Output is correct
22	Correct	4 ms	8148 KB	Output is correct
23	Correct	4 ms	8148 KB	Output is correct
24	Correct	3 ms	8148 KB	Output is correct
25	Correct	3 ms	8148 KB	Output is correct
26	Correct	3 ms	8148 KB	Output is correct
27	Correct	3 ms	8148 KB	Output is correct
28	Correct	3 ms	8148 KB	Output is correct
29	Correct	3 ms	8148 KB	Output is correct
30	Correct	3 ms	8148 KB	Output is correct
31	Correct	3 ms	8148 KB	Output is correct
32	Correct	3 ms	8148 KB	Output is correct
33	Correct	3 ms	8148 KB	Output is correct
34	Correct	4 ms	8076 KB	Output is correct
35	Correct	55 ms	11988 KB	Output is correct
36	Correct	52 ms	12000 KB	Output is correct
37	Correct	52 ms	12044 KB	Output is correct
38	Correct	52 ms	12020 KB	Output is correct
39	Correct	48 ms	12008 KB	Output is correct
40	Correct	49 ms	11940 KB	Output is correct
41	Correct	51 ms	11984 KB	Output is correct
42	Correct	49 ms	12000 KB	Output is correct
43	Correct	46 ms	11960 KB	Output is correct
44	Correct	58 ms	12012 KB	Output is correct
45	Correct	47 ms	11976 KB	Output is correct
46	Correct	45 ms	12044 KB	Output is correct
47	Correct	49 ms	12012 KB	Output is correct
48	Correct	50 ms	12004 KB	Output is correct
49	Correct	50 ms	11980 KB	Output is correct
50	Correct	60 ms	11976 KB	Output is correct
51	Correct	68 ms	12040 KB	Output is correct
52	Correct	68 ms	12060 KB	Output is correct
53	Correct	65 ms	11960 KB	Output is correct
54	Correct	62 ms	11980 KB	Output is correct
55	Correct	65 ms	11928 KB	Output is correct
56	Correct	61 ms	11928 KB	Output is correct
57	Correct	58 ms	12016 KB	Output is correct
58	Correct	60 ms	12060 KB	Output is correct
59	Correct	63 ms	12024 KB	Output is correct
60	Correct	56 ms	12000 KB	Output is correct
61	Correct	13 ms	8148 KB	Output is correct
62	Correct	9 ms	8152 KB	Output is correct
63	Correct	16 ms	8148 KB	Output is correct
64	Correct	12 ms	8148 KB	Output is correct
65	Correct	43 ms	10028 KB	Output is correct
66	Correct	31 ms	9440 KB	Output is correct
67	Correct	67 ms	11308 KB	Output is correct
68	Correct	10 ms	8512 KB	Output is correct
69	Correct	18 ms	8152 KB	Output is correct
70	Correct	4 ms	8148 KB	Output is correct
71	Correct	11 ms	8152 KB	Output is correct

답안 #795780

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 3.0 / 3.0

Subtask #3 4.0 / 4.0

Subtask #4 4.0 / 4.0

Subtask #5 4.0 / 4.0

Subtask #6 7.0 / 7.0

Subtask #1
3.0 / 3.0

Subtask #2
3.0 / 3.0

Subtask #3
4.0 / 4.0

Subtask #4
4.0 / 4.0

Subtask #5
4.0 / 4.0

Subtask #6
7.0 / 7.0