Submission #1252291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252291		_rain_	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	87 ms	70728 KiB

kangaroo

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

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>(x))&(1))

template<class X , class Y>
	bool maximize(X &x , Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x, Y y){
		if (x>y) return x=y,true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end()) ; 
		data.resize(unique(data.begin() , data.end()) - data.begin());
		return;
	}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	int Rand(int l,int r){
		return uniform_int_distribution<int>(l,r)(rng);
	}

const int N = (int)2000;
const int MOD = (int)1e9+7;
	int add(int a,int b){
		return a + b >= MOD ?a + b - MOD : a + b;
	}
	
	int mul(int a,int b){
		return (LL)a*b % MOD;
	}
	
	int start , finish , n;
	int dp[N+2][N+2][2][2][2] = {};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
	
		cin >> n >> start >> finish;
		dp[0][0][0][0][0] = 1;
		FOR(i,0,n-1){
			FOR(cur_comp , 0 , i) FOR(have_start , 0 , 1) FOR(have_end , 0 , 1) {
				bool nxt_start = have_start | (i + 1 == start);
				bool nxt_end = have_end | (i + 1 == finish);
				//... create a new component
					int &xx = dp[i+1][cur_comp+1][nxt_start][nxt_end][0];
					xx = add(xx , dp[i][cur_comp][have_start][have_end][0]);
				//... insert start and finish positions
					int &x1 = dp[i+1][cur_comp][nxt_start][nxt_end][0];
					int &x2 = dp[i+1][cur_comp][nxt_start][nxt_end][1];
					LL tt = dp[i][cur_comp][have_start][have_end][0];
					
					if (i + 1 == start && cur_comp == 1 && have_end){
						x2 = add(x2 , tt);
					}	
					else if (i + 1 == finish && cur_comp == 1 && have_start){
						x2 = add(x2 , tt);
					}
					if (i + 1 == start){
						x1 = add(x1 , tt * (cur_comp - have_end) % MOD);
					}
					if (i + 1 == finish){
						x1 = add(x1 , tt * (cur_comp - have_start) % MOD);
					}
					
				//... merging two components together
				if (cur_comp > 1 && i + 1 != start && i + 1 != finish){
					int rest_comp = cur_comp - have_start - have_end;
					LL t = dp[i][cur_comp][have_start][have_end][0];
					int &t1 = dp[i+1][cur_comp-1][have_start][have_end][0];
					int &t2 = dp[i+1][cur_comp-1][have_start][have_end][1];
					t1 = add(t1 , (LL)t * rest_comp * (rest_comp - 1) % MOD);
					if (have_start) {
						t1 = add(t1 , (LL)t * rest_comp % MOD);
					}
					if (have_end){
						t1 = add(t1 , (LL)t * rest_comp % MOD);
					} 
					if (have_start && have_end && cur_comp == 2) {
						t2 = add(t2 , t);
					}
				}
		}
	}
	cout<<dp[n][1][1][1][1];
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:47:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kangaroo.cpp:48:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49