Submission #967977

#	Time	Username	Problem	Language	Result	Execution time	Memory
967977		willychan	Binaria (CCO23_day1problem1)	C++17	18 / 25	1031 ms	68944 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;
	for(int i=0;i<k;i++){
		if(hasto[i]==1) cnt++;
		if(hasto[i]==-1){
			stuff[d.query(i)]++;
		}
	}
	int K = arr[0]-cnt;
	map<int,int> btw;
	for(auto i : stuff) btw[i.second]++;
	vector<pair<int,int> > w;			
	for(auto i : btw) w.push_back(i);
	w.push_back({0,0});
	sort(w.begin(),w.end());
	vector<vector<int>> dp(w.size(),vector<int>(K+1,0));
	dp[0][0]=1;
	for(int i=1;i<w.size();i++){
		for(int j=0;j<=K;j++){
			for(int h=0;h<=w[i].second;h++){
				if(j<h*w[i].first) break;
				dp[i][j]  = (dp[i][j]+((1LL*C(w[i].second,h)*dp[i-1][j-h*w[i].first])%MOD))%MOD;
			}
		}
	}
	cout<<dp[w.size()-1][K]<<"\n";
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:97:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i=1;i<w.size();i++){
      |              ~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 7