Submission #1231083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231083		g4yuhg	Binaria (CCO23_day1problem1)	C++20	25 / 25	574 ms	94280 KiB

Main

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 1000006
using namespace std;

bool ghuy4g; 

ll par[N];

ll getRoot(ll u) {
    if (par[u] < 0) return u;
    par[u] = getRoot(par[u]);
    return par[u];
}

void join(ll u, ll v) {
    u = getRoot(u);
    v = getRoot(v);
    if (u == v) return;
    if (par[u] < par[v]) {
        par[u] += par[v];
        par[v] = u;
    }
    else {
        par[v] += par[u];
        par[u] = v;
    }
}

ll n, k;
ll b[N], a[N];

const ll mod = 1e6 + 3;

ll gt[1000006], INV[1000006];
ll POW(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    ll t = POW(a, b / 2, mod);
    t = t * t % mod;
    if (b % 2 == 1) {
        t = t * a % mod;
    }
    return t;
}
ll inv(ll a, ll mod) {
    return POW(a, mod - 2, mod);
}
void pre() {
    gt[0] = 1;
    for (int i = 1; i <= 1e6; i ++) {
        gt[i] = gt[i - 1] * i % mod;
        INV[i] = inv(gt[i], mod);
    }
}
ll C(ll n, ll k, ll mod) {
    if (k == n || k == 0) return 1;
    return gt[n] * INV[k] % mod * INV[n - k] % mod;
} 



bool klinh;

signed main(void) {
	memset(par, -1, sizeof(par));
	memset(a, -1, sizeof(a));
	pre();
    faster;
	cin >> n >> k;
	for (int i = 1; i <= n - k + 1; i ++) {
		cin >> b[i];
	}
	for (int i = 1; i < n - k + 1; i ++) {
		if (b[i] == b[i + 1]) {
			join(i, i + k);
		}
		else if (b[i] == b[i + 1] + 1) {
			if (a[i] != -1 && a[i] == 0) {
				cout << 0;
				return 0;
			}
			a[i] = 1;
			if (a[i + k] != -1 && a[i + k] == 1) {
				cout << 0;
				return 0;
			}
			a[i + k] = 0;
		}
		else if (b[i] + 1 == b[i + 1]) {
			if (a[i] != -1 && a[i] == 1) {
				cout << 0;
				return 0;
			}
			a[i] = 0;
			if (a[i + k] != -1 && a[i + k] == 0) {
				cout << 0;
				return 0;
			}
			a[i + k] = 1;
		}
	}
	for (int i = 1; i <= n; i ++) {
		if (a[i] == -1) continue;
		ll root = getRoot(i);
		if (a[root] != -1 && a[root] != a[i]) {
			cout << 0;
			return 0;
		}
		a[getRoot(i)] = a[i];
	}
	map<ll, ll> mp;
	ll sum = 0, cnt = 0;
	for (int i = 1; i <= k; i ++) {
		ll r = getRoot(i);
		if (a[r] == 1) sum += 1;
		else if (a[r] == 0) sum += 0;
		else {
			//cout << i << " root " << r << " " << a[r] << endl;
			mp[r] ++ ;
			if (mp[r] > 1) {
				cout << "ngu";
				return 0;
			}
			cnt ++ ;
		}
	}
	ll left = b[1] - sum;
	//cout << cnt << " " << left << endl;
	cout << C(cnt, left, mod);
	
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    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