oj.uz

Submission #1026182

# Submission time Handle Problem Language Result Execution time Memory
1026182 2024-07-17T16:47:34 Z _rain_ Binaria (CCO23_day1problem1) C++14
3 / 25
 12 ms 10716 KB 
#include<bits/stdc++.h>
using namespace std;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
namespace Random
{
	#define int long long
	int Rand(int l , int r)
		{
			return uniform_int_distribution<int>(l , r)(rng);
		} 
	#undef int 
}

using i64 = long long;
using ui64 = unsigned long long;

#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (x).size()
#define all(x) (x).begin() , (x).end()

#define FOR(i ,a , b) for (int i = (a); i <= (b); ++i)
#define FORD(i , a , b) for (int i = (b); i >= (a); --i)
#define REP(i , a , b) for (int i = (a); i < (b); ++i)
#define REPD(i , a , b) for (int i = (b) - 1 ; i >= (a); --i)

template <class T> 
    void compress(vector<T> &a)
    {
        sort(a.begin() , a.end());
        a.resize(unique(a.begin() , a.end()) - a.begin());
        return;
    }
template<class T>
    void printArr(T& container , string separator = "" , string finish = "\n")
    {
        for (auto& item : container) cout << item << separator;
        cout << finish;
    }
template<class T>
    bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
    bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
    T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
    T lcm(T x , T y) {return (x * y) / gcd(x , y);}

//... INPUT
    void INPUT(string name)
    {
    	iostream::sync_with_stdio(false); cin.tie(0);
    	if (!fopen((name + ".inp").c_str() , "r")) return;
    	freopen((name + ".inp").c_str() , "r" , stdin);
    	freopen((name + ".out").c_str() , "w+" , stdout);
    	return;
    }

const int maxn = 1e6;
int a[maxn + 2] ;
int n , k;

//... MOD OPERATOR
	const int MOD = 1e6 + 3;
	int add(int a , int b)
	{
		return (a + b >= MOD ? a + b - MOD : a + b);
	}
	int mul(int a , int b)
	{
		return (i64)a * b % MOD;
	}
	int _pow(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[maxn + 2] , inv[maxn + 2];
	void pre()
	{
		fac[0] = 1;
		FOR(i,1,maxn) fac[i] = mul(fac[i - 1] , i);
		inv[maxn] = _pow(fac[maxn] , MOD - 2);
		FORD(i,1,maxn) inv[i - 1] = mul(inv[i] , i);
		return;
	}
	int C(int x , int y)
	{
		if (x > y) return 0;
		return fac[y] * inv[x] % MOD * inv[y - x] % MOD;
	}
int s[maxn + 2] ;

int32_t main()
{
	INPUT("main");
		cin >> n >> k;
		pre();
		FOR(i,1,n-k+1) cin >> a[i];
		FOR(i,1,n) s[i] = -1;
		FORD(i,1,n-k)
		{
			if (abs(a[i] - a[i + 1]) == 0) s[i] = s[i + k];
			if (abs(a[i] - a[i + 1]) == 1) 
			{
				if (a[i] > a[i + 1])
				{
					if (s[i + k] == 1)
					{
						cout << 0;
						return 0;
					}
					s[i] = 1;
				}
				if (a[i] < a[i + 1])
				{
					if (s[i + k] == 0)
					{
						cout << 0;
						return 0;
					}
					s[i] = 0;
				}
			}
			if (abs(a[i] - a[i + 1]) >= 2)
					{
						cout << 0;
						return 0;
					}
		}
		int answer = 0 , s1 = a[1] , s2 = 0;
		FOR(i,1,k)
		{
			if (s[i] == 1) s1--;
				else if (s[i] == -1) ++s2;
		}
		cout << C(s1 , s2);
	cerr << "\nTIME RUN : " << 1000 * clock() / CLOCKS_PER_SEC << "MS\n";
	return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:134:7: warning: unused variable 'answer' [-Wunused-variable]
  134 |   int answer = 0 , s1 = a[1] , s2 = 0;
      |       ^~~~~~
Main.cpp: In function 'void INPUT(std::string)':
Main.cpp:55:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |      freopen((name + ".inp").c_str() , "r" , stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:56:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |      freopen((name + ".out").c_str() , "w+" , stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10588 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct
3 Correct 11 ms 10716 KB Output is correct
4 Correct 11 ms 10584 KB Output is correct
5 Correct 11 ms 10584 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 11 ms 10588 KB Output is correct
8 Correct 11 ms 10588 KB Output is correct
9 Correct 11 ms 10584 KB Output is correct
10 Correct 11 ms 10588 KB Output is correct
11 Correct 11 ms 10588 KB Output is correct
12 Correct 11 ms 10588 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10588 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct
3 Correct 11 ms 10716 KB Output is correct
4 Correct 11 ms 10584 KB Output is correct
5 Correct 11 ms 10584 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 11 ms 10588 KB Output is correct
8 Correct 11 ms 10588 KB Output is correct
9 Correct 11 ms 10584 KB Output is correct
10 Correct 11 ms 10588 KB Output is correct
11 Correct 11 ms 10588 KB Output is correct
12 Correct 11 ms 10588 KB Output is correct
13 Incorrect 11 ms 10584 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10588 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct
3 Correct 11 ms 10716 KB Output is correct
4 Correct 11 ms 10584 KB Output is correct
5 Correct 11 ms 10584 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 11 ms 10588 KB Output is correct
8 Correct 11 ms 10588 KB Output is correct
9 Correct 11 ms 10584 KB Output is correct
10 Correct 11 ms 10588 KB Output is correct
11 Correct 11 ms 10588 KB Output is correct
12 Correct 11 ms 10588 KB Output is correct
13 Incorrect 11 ms 10584 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10588 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct
3 Correct 11 ms 10716 KB Output is correct
4 Correct 11 ms 10584 KB Output is correct
5 Correct 11 ms 10584 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 11 ms 10588 KB Output is correct
8 Correct 11 ms 10588 KB Output is correct
9 Correct 11 ms 10584 KB Output is correct
10 Correct 11 ms 10588 KB Output is correct
11 Correct 11 ms 10588 KB Output is correct
12 Correct 11 ms 10588 KB Output is correct
13 Incorrect 11 ms 10584 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10588 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct
3 Correct 11 ms 10716 KB Output is correct
4 Correct 11 ms 10584 KB Output is correct
5 Correct 11 ms 10584 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 11 ms 10588 KB Output is correct
8 Correct 11 ms 10588 KB Output is correct
9 Correct 11 ms 10584 KB Output is correct
10 Correct 11 ms 10588 KB Output is correct
11 Correct 11 ms 10588 KB Output is correct
12 Correct 11 ms 10588 KB Output is correct
13 Incorrect 11 ms 10584 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10588 KB Output is correct
2 Correct 11 ms 10588 KB Output is correct
3 Correct 11 ms 10716 KB Output is correct
4 Correct 11 ms 10584 KB Output is correct
5 Correct 11 ms 10584 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 11 ms 10588 KB Output is correct
8 Correct 11 ms 10588 KB Output is correct
9 Correct 11 ms 10584 KB Output is correct
10 Correct 11 ms 10588 KB Output is correct
11 Correct 11 ms 10588 KB Output is correct
12 Correct 11 ms 10588 KB Output is correct
13 Incorrect 11 ms 10584 KB Output isn't correct
14 Halted 0 ms 0 KB -