oj.uz

Submission #792401

# Submission time Handle Problem Language Result Execution time Memory
792401 2023-07-25T04:13:58 Z 박상훈(#10052) Binaria (CCO23_day1problem1) C++17
0 / 25
 12 ms 23832 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int MOD = 1e6 + 3;
int S[1001000];
vector<int> V[1001000];
ll fact[1001000], factINV[1001000];

void NO(){
	printf("0\n");
	exit(0);
}

ll pw(ll a, ll e){
	if (!e) return 1;
	ll ret = pw(a, e/2);
	if (e&1) return ret * ret % MOD * a % MOD;
	return ret * ret % MOD;
}

ll ncr(int n, int r){
	// printf("ok %d %d\n", n, r);
	fact[0] = 1;
	for (int i=1;i<=n;i++) fact[i] = fact[i-1] * i % MOD;
	for (int i=0;i<=n;i++) factINV[i] = pw(fact[i], MOD-2);
	return fact[n] * factINV[r] % MOD * factINV[n-r] % MOD;
}

int main(){
	int n, k;
	scanf("%d %d", &n, &k);

	for (int i=1;i<=n-k+1;i++) scanf("%d", S+i);
	for (int i=0;i<k;i++) V[i].push_back(-1);

	for (int i=1;i<=n-k;i++){
		if (S[i]==S[i+1]) V[i%k].push_back(-1);
		else if (S[i]+1 == S[i+1]){
			if (V[i%k].back()==1) NO();
			if (V[i%k].back()==-1){
				for (auto &x:V[i%k]) x = 0;
			}
			V[i%k].push_back(1);
		}
		else if (S[i] == S[i+1]+1){
			if (V[i%k].back()==0) NO();
			if (V[i%k].back()==-1){
				for (auto &x:V[i%k]) x = 1;
			}
			V[i%k].push_back(0);
		}

		else NO();
	}

	// for (int i=0;i<k;i++){
	// 	printf("%d: ", i);
	// 	for (auto &x:V[i]) printf("%d ", x);
	// 	printf("\n");
	// }

	int mn = 0, mx = 0;
	for (int i=0;i<k;i++){
		if (V[i][0]==1) mn++, mx++;
		else if (V[i][0]==-1) mx++;
	}

	if (mn <= S[1] && S[1] <= mx){
		int N = mx - mn;
		int R = S[1] - mn;
		printf("%lld\n", ncr(N, R));
	}
	else NO();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:35:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  for (int i=1;i<=n-k+1;i++) scanf("%d", S+i);
      |                             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Incorrect 12 ms 23748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Incorrect 12 ms 23748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Incorrect 12 ms 23748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Incorrect 12 ms 23748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Incorrect 12 ms 23748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Incorrect 12 ms 23748 KB Output isn't correct
7 Halted 0 ms 0 KB -