Submission #1252282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252282		_rain_	Kangaroo (CEOI16_kangaroo)	C++20	0 / 100	0 ms	324 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) FOR(connect , 0 , 1){
				if (connect) continue;
				bool nxt_start = have_start | (i + 1 == start);
				bool nxt_end = have_end | (i + 1 == finish);
				//... create a new component
					dp[i + 1][cur_comp + 1][nxt_start][nxt_end][0] = add(dp[i+1][cur_comp + 1][nxt_start][nxt_end][0] , dp[i][cur_comp][have_start][have_end][0]);
				//... insert start and finish positions
					if (i + 1 == start && have_end && cur_comp==1) {
						dp[i+1][cur_comp][nxt_start][nxt_end][1] = add(dp[i+1][cur_comp][nxt_start][nxt_end][1] , dp[i][cur_comp][have_start][have_end][0]);
					}
					else 
					if (i + 1 == finish && have_start && cur_comp==1){
						dp[i+1][cur_comp][nxt_start][nxt_end][1] = add(dp[i+1][cur_comp][nxt_start][nxt_end][1] , dp[i][cur_comp][have_start][have_end][0]);
					}
					else 
					if (i + 1 == start  && have_start == 0){
						dp[i+1][cur_comp][1][nxt_end][0] = add(dp[i+1][cur_comp][1][nxt_end][0] , (LL)dp[i][cur_comp][0][nxt_end][0] * (cur_comp - nxt_end) % MOD);
					}
					else 
					if (i + 1 == finish && have_end == 0){
						dp[i+1][cur_comp][nxt_start][1][0] = add(dp[i+1][cur_comp][nxt_start][1][0] , (LL)dp[i][cur_comp][nxt_start][0][0] * (cur_comp - nxt_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];
					dp[i+1][cur_comp-1][have_start][have_end][0] = add(dp[i+1][cur_comp-1][have_start][have_end][0] , (LL)t * rest_comp * (rest_comp - 1) % MOD);
					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) {
						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: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49