oj.uz

Submission #932881

# Submission time Handle Problem Language Result Execution time Memory
932881 2024-02-24T10:42:20 Z PotatoMan Binaria (CCO23_day1problem1) C++14
0 / 25
 1 ms 348 KB 
#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod 1000003
#define MAXN 200005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;
 
ll n,k,m,q,cur;
ll ans = 0;
string subtask;
int tc = 1;

ll binpow(ll x,ll y){
	if( y == 0 ) return 1;
	ll res = binpow(x,y/2);
	res *= res;
	res %= mod;
	if( y % 2 ) res *= x;
	return res%mod;
}

void solve(){
	cin>>n>>k;
	ll a[n];
	ll m = n-k+1;
	for(int i = 0 ; i < m ; i++){
		cin>>a[i];
	}
	int v[n+5];
	for(int i = 0 ; i < n ; i++) v[i] = 2;
	for(int i = m-2 ; i >= 0 ; i--){
		if( a[i] == a[i+1]-1 ) {
			if( v[i+k] == 0 ){
				cout<<0<<"\n";
				return;
			}
			v[i] = 0;
		}
		else if( a[i] == a[i+1]+1 ) {
			if( v[i+k] == 1 ){
				cout<<0<<"\n";
				return;
			}
			v[i] = 1;
		}
		else if( a[i] == a[i+1] ){
			v[i+k] = v[i];
		}
		else if( abs(a[i]-a[i+1]) > 1 ){
			cout<<0<<"\n";
			return;
		} 
	}
	ll x = 0, c = a[0];
	for(int i = 0 ; i < k ; i++){
		if( v[i] == 1 ) c--;
		if( v[i] == 2 ) x++;
	}
	if( x-c < 0 || c < 0 ) {
		cout<<0<<"\n";
		return;
	}
	ll fact[k+5];
	fact[0] = fact[1] = 1;
	for(ll i = 2 ; i <= x ; i++){
		fact[i] = fact[i-1]*i;
		fact[i] %= mod;
	}
	ans = fact[x];
	ll foo = (fact[c]*fact[x-c])%mod;
	ans *= binpow(foo,mod-2);
	cout<<ans%mod<<"\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
		tc++;
	}
	return 0;
}
 
/*
	same val different variable 
	swapped multidimentional size
	out of bound for loop
	(constraint change in loop)
	forget to change bool to int
	misread -> missed subtask
	you thought u declared it huh?
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 7.0

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