Submission #967987

#	Time	Username	Problem	Language	Result	Execution time	Memory
967987		willychan	Binaria (CCO23_day1problem1)	C++17	25 / 25	77 ms	25172 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int MOD = 1e6+3;

struct dsu{
	vector<int> arr;
	int n;
	void init(int _n){
		 n = _n;	
		 arr.resize(n);
		 for(int i=0;i<n;i++) arr[i]=i;
	}
	int query(int a){
		if(arr[a]==a) return a;
		arr[a] = query(arr[a]);
		return arr[a];
	}
	void join(int a,int b){
		a = query(a);
		b = query(b);
		if(a!=b) arr[a]=b;
	}
};

vector<int> fac;
vector<int> invfac;

int C(int n,int k){
	ll r = 1LL*((1LL*fac[n]*invfac[k])%MOD)*invfac[n-k]%MOD;
	return r;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,k;cin>>n>>k;	
	fac.resize(k+1);
	invfac.resize(k+1);
	fac[0]=1;
	for(int i=1;i<=k;i++) fac[i] = (1LL*fac[i-1]*i)%MOD;
	ll g = fac[k];
	ll r = 1;
	ll p = MOD-2;
	while(p){
		if(p&1) r = (r*g)%MOD;
		g = (g*g)%MOD;
		p>>=1;
	}
	invfac[k]=r;
	for(int i=k;i>=1;i--){
		invfac[i-1] = (1LL*invfac[i]*i)%MOD;
	}
	vector<int> arr(n-k+1);
	for(int i=0;i<n-k+1;i++){
		cin>>arr[i];
	}
	dsu d;
	d.init(n);
	vector<int> hasto(n,-1);
	for(int i=0;i<n-k;i++){
		if(arr[i]==arr[i+1]){
			d.join(i,i+k);
		}else if(arr[i]+1==arr[i+1]){
			hasto[i]=0;
			hasto[i+k]=1;
		}else{
			hasto[i]=1;
			hasto[i+k]=0;
		}
	}
	for(int i=0;i<n;i++)	{
		int a = d.query(i);
		if(hasto[i]!=-1) hasto[a]=hasto[i];
	}
	for(int i=0;i<n;i++)	{
		hasto[i] = hasto[d.query(i)];
	}
	map<int,int> stuff;
	int cnt = 0;
	int cnt2 = 0;
	for(int i=0;i<k;i++){
		if(hasto[i]==1) cnt++;
		if(hasto[i]==-1){
			cnt2++;
		}
	}
	int K = arr[0]-cnt;
	cout<<C(cnt2,K)<<"\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