oj.uz

Submission #865741

# Submission time Handle Problem Language Result Execution time Memory
865741 2023-10-24T15:04:25 Z _hbk06 Binaria (CCO23_day1problem1) C++14
0 / 25
 6 ms 6748 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "task"

using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e6 + 3;
const long long infll = 1e18 + 6969;

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

struct MST {
	int n;
	vector<int>par;
	MST(int _n) {
		n = _n;
		par.assign(n + 2,-1);
	}

	int get_root(int u) {
		if(par[u] < 0) return u;
		return par[u] = get_root(par[u]);
	}

	void merge(int u,int v) {
		u = get_root(u);
		v = get_root(v);
		if(u == v) return;
		if(par[u] > par[v]) swap(u,v);
		par[u] += par[v];
		par[v] = u;
	}
};

int n;
int k;
int a[mxN];
int bit[mxN];
int adj[mxN];
int frac[mxN];

int Pow(int n,int k) {
    if(k == 1) return n % Mod;
    ll tmp = Pow(n,(k >> 1)) % Mod;
    tmp = (tmp * tmp) % Mod;
    if(k & 1) tmp = (tmp * n) % Mod;
    return tmp;
}

void fractorize() {
    frac[0] = 1;
    for(int i = 1;i <= mxN;i++)
        frac[i] = (1LL * frac[i - 1] * i) % Mod;
    adj[mxN] = Pow(frac[mxN],Mod - 2);
    for(int i = mxN;i > 0;i--)
        adj[i - 1] = (1LL * adj[i] * i) % Mod;
}

int Ckn(int k,int n) {
    if(k > n) return 0LL;
    return 1LL * (frac[n] * adj[k] % Mod * adj[n - k] % Mod);
}

void solve() {
	cin >> n >> k;
	fractorize();
	for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
	memset(bit,-1,sizeof bit);
	MST dsu(n + 2);
	for (int i = 1; i <= n - k; i++) {
		if(a[i] < a[i + 1]) {
			int u = dsu.get_root(i);
			int v = dsu.get_root(i + k);
			bit[u] = 0;
			bit[v] = 1;
		}
		if(a[i] > a[i + 1]) {
			int u = dsu.get_root(i);
			int v = dsu.get_root(i + k);
			bit[u] = 1;
			bit[v] = 0;
		}
		else dsu.merge(i,i + k);
	}
	int cnt = 0;
	for (int i = 1; i <= k; i++) {
		int u = dsu.get_root(i);
		if(bit[u] < 0) cnt++;
		else a[1] -= bit[u];
	}
	cout << Ckn(a[1],cnt);
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

Compilation message

Main.cpp: In function 'void fractorize()':
Main.cpp:69:17: warning: iteration 500006 invokes undefined behavior [-Waggressive-loop-optimizations]
   69 |         frac[i] = (1LL * frac[i - 1] * i) % Mod;
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:68:21: note: within this loop
   68 |     for(int i = 1;i <= mxN;i++)
      |                   ~~^~~~~~
Main.cpp:70:19: warning: array subscript 500007 is above array bounds of 'int [500007]' [-Warray-bounds]
   70 |     adj[mxN] = Pow(frac[mxN],Mod - 2);
      |                ~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:56:5: note: while referencing 'frac'
   56 | int frac[mxN];
      |     ^~~~
Main.cpp:70:12: warning: array subscript 500007 is above array bounds of 'int [500007]' [-Warray-bounds]
   70 |     adj[mxN] = Pow(frac[mxN],Mod - 2);
      |     ~~~~~~~^
Main.cpp:55:5: note: while referencing 'adj'
   55 | int adj[mxN];
      |     ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 6 ms 6744 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Incorrect 6 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 6 ms 6744 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Incorrect 6 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 6 ms 6744 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Incorrect 6 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 6 ms 6744 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Incorrect 6 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 6 ms 6744 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Incorrect 6 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 6 ms 6744 KB Output is correct
3 Correct 6 ms 6748 KB Output is correct
4 Incorrect 6 ms 6744 KB Output isn't correct
5 Halted 0 ms 0 KB -