oj.uz

Submission #1026161

# Submission time Handle Problem Language Result Execution time Memory
1026161 2024-07-17T16:13:58 Z _rain_ Binaria (CCO23_day1problem1) C++14
3 / 25
 16 ms 37396 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] , ID[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;
	}
vector<int> bag[maxn + 2];
int s[maxn + 2] ;

int32_t main()
{
	INPUT("main");
		cin >> n >> k;
		pre();
		FOR(i,k,n) cin >> a[i];
		FOR(i,1,n) s[i] = -1;
		FOR(i,1,k) 
			{
				ID[i] = i;
				bag[ID[i]].push_back(i);
			}
		FOR(i,k+1,n)
		{
			if (abs(a[i] - a[i - 1]) == 0)
			{
				if (ID[i - k] == 0) s[i] = s[i - k];
					else 
					{
						ID[i] = ID[i - k];
						bag[ID[i]].push_back(i);
					}
				continue;
			}
			if (abs(a[i] - a[i - 1]) == 1)
			{
				if (a[i] > a[i - 1])
				{
					if (ID[i - k] == 0) s[i - k] = 0;
						else 
						{
							for (auto& x : bag[ID[i - k]]) s[x] = 0;
							bag[ID[i - k]].clear(); ID[i - k] = 0;
						}
					s[i] = 1;
				}
				if (a[i] < a[i - 1])
				{
					if (ID[i - k] == 0) s[i - k] = 1;
						else 
						{
							for (auto& x : bag[ID[i - k]]) s[x] = 1;
								bag[ID[i - k]].clear(); ID[i - k] = 0;
						}
					s[i] = 0;
				}
				continue;
			}
			cout << 0;
			return 0;
		}
		int answer = 0;
		FOR(i,1,k)
		{
			if (s[i] != -1) a[k] -= s[i];
				else ++answer;
		}
		cout << C(a[k] , answer);
	cerr << "\nTIME RUN : " << 1000 * clock() / CLOCKS_PER_SEC << "MS\n";
	return 0;
}

Compilation message

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 15 ms 37208 KB Output is correct
2 Correct 14 ms 37212 KB Output is correct
3 Correct 15 ms 37396 KB Output is correct
4 Correct 15 ms 37396 KB Output is correct
5 Correct 15 ms 37396 KB Output is correct
6 Correct 16 ms 37212 KB Output is correct
7 Correct 15 ms 37392 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Correct 15 ms 37208 KB Output is correct
10 Correct 15 ms 37340 KB Output is correct
11 Correct 14 ms 37212 KB Output is correct
12 Correct 15 ms 37212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37208 KB Output is correct
2 Correct 14 ms 37212 KB Output is correct
3 Correct 15 ms 37396 KB Output is correct
4 Correct 15 ms 37396 KB Output is correct
5 Correct 15 ms 37396 KB Output is correct
6 Correct 16 ms 37212 KB Output is correct
7 Correct 15 ms 37392 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Correct 15 ms 37208 KB Output is correct
10 Correct 15 ms 37340 KB Output is correct
11 Correct 14 ms 37212 KB Output is correct
12 Correct 15 ms 37212 KB Output is correct
13 Incorrect 15 ms 37208 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37208 KB Output is correct
2 Correct 14 ms 37212 KB Output is correct
3 Correct 15 ms 37396 KB Output is correct
4 Correct 15 ms 37396 KB Output is correct
5 Correct 15 ms 37396 KB Output is correct
6 Correct 16 ms 37212 KB Output is correct
7 Correct 15 ms 37392 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Correct 15 ms 37208 KB Output is correct
10 Correct 15 ms 37340 KB Output is correct
11 Correct 14 ms 37212 KB Output is correct
12 Correct 15 ms 37212 KB Output is correct
13 Incorrect 15 ms 37208 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37208 KB Output is correct
2 Correct 14 ms 37212 KB Output is correct
3 Correct 15 ms 37396 KB Output is correct
4 Correct 15 ms 37396 KB Output is correct
5 Correct 15 ms 37396 KB Output is correct
6 Correct 16 ms 37212 KB Output is correct
7 Correct 15 ms 37392 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Correct 15 ms 37208 KB Output is correct
10 Correct 15 ms 37340 KB Output is correct
11 Correct 14 ms 37212 KB Output is correct
12 Correct 15 ms 37212 KB Output is correct
13 Incorrect 15 ms 37208 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37208 KB Output is correct
2 Correct 14 ms 37212 KB Output is correct
3 Correct 15 ms 37396 KB Output is correct
4 Correct 15 ms 37396 KB Output is correct
5 Correct 15 ms 37396 KB Output is correct
6 Correct 16 ms 37212 KB Output is correct
7 Correct 15 ms 37392 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Correct 15 ms 37208 KB Output is correct
10 Correct 15 ms 37340 KB Output is correct
11 Correct 14 ms 37212 KB Output is correct
12 Correct 15 ms 37212 KB Output is correct
13 Incorrect 15 ms 37208 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37208 KB Output is correct
2 Correct 14 ms 37212 KB Output is correct
3 Correct 15 ms 37396 KB Output is correct
4 Correct 15 ms 37396 KB Output is correct
5 Correct 15 ms 37396 KB Output is correct
6 Correct 16 ms 37212 KB Output is correct
7 Correct 15 ms 37392 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Correct 15 ms 37208 KB Output is correct
10 Correct 15 ms 37340 KB Output is correct
11 Correct 14 ms 37212 KB Output is correct
12 Correct 15 ms 37212 KB Output is correct
13 Incorrect 15 ms 37208 KB Output isn't correct
14 Halted 0 ms 0 KB -