Submission #1151978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151978		_rain_	Binaria (CCO23_day1problem1)	C++17	0 / 25	33 ms	55112 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

const int N=(int)1e6;
	vector<int>ke[N+2],comp[N+2];
	int a[N+2],id[N+2],cc[N+2];
	int n,k;
const int MOD=(int)1e6+3;
	int add(int a,int b){
		return a+b>=MOD?a+b-MOD:a+b;
	}
	int sub(int a,int b){
		return a-b<0?a-b+MOD:a-b;
	}
	int mul(int a,int b){
		return (LL)a*b%MOD;
	}
	int power(int a,int b){
		int res=1;
		for(;b;b>>=1,a=mul(a,a))
			if (b&1) res=mul(res,a);
		return res;
	}
	
	int fac[N+2],inv[N+2];
	
	void build(){
		fac[0]=1;
		FOR(i,1,N) fac[i]=mul(fac[i-1],i);
		inv[N]=power(fac[N],MOD-2);
		FORD(i,1,N) inv[i-1]=mul(inv[i],i);
		return;
	}
	int C(int x,int y){
		if (x>y) return 0;
		return (LL)fac[y]*inv[y-x]*inv[x]%MOD;
	}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>k;
	build();
	int size=n-k+1;
	FOR(i,k,n) cin>>a[i];
	FOR(i,1,n) id[i]=i,cc[i]=-1;
	FOR(i,1,k) comp[i].push_back(i);
	FOR(i,k+1,n) {
		int previd=i-k;
		if (a[i]==a[i-1]) {
			if (cc[id[previd]]!=-1) cc[i]=cc[id[previd]];
				else comp[id[previd]].push_back(i);
			id[i]=id[previd];
		}
		if (a[i]==a[i-1]+1){
			assert(cc[id[previd]]!=1);
			for(auto&x:comp[id[previd]]) cc[x]=0;
			comp[id[previd]].clear();
			cout<<i<<'\n';
			cc[i]=1;
		}
		if (a[i]==a[i-1]-1){
			assert(cc[id[previd]]!=0);
			for(auto&x:comp[id[previd]]) cc[x]=1;
			comp[id[previd]].clear();
			cc[i]=0;
		}
	}
	int cnt=0;
	FOR(i,1,k) if (cc[i]!=-1) a[k]-=cc[i]; else ++cnt;
	cout<<C(a[k],cnt);
	exit(0);
}

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