Submission #1173368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173368		Nurislam	Kangaroo (CEOI16_kangaroo)	C++20	6 / 100	2095 ms	324 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;


#define int long long
#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;

struct bitt {
	vector<int> t;
	int n;
	bitt (int N) : n(N+1) {
		t.resize(n+2);
	};
	
	void upd(int i, int va) { i ++ ;
		for(; i < n; i += (i & -i)) t[i] += va;
	};
	
	int get(int i) { i ++ ;
		int res = 0;
		for(; i > 0; i -= (i & -i)) res += t[i];
		return res;
	};
	
	int get(int l, int r) { r--;
		return get(r ) - get( -- l );
	};
};

void solve(){
	int n, s, f;
	cin >> n >> s >> f;
	
	vector<int> a(n);
	iota(a.begin(), a.end(), 1);
	
	int ans = 0;
	do {
		if(a[0] != s || a[n-1] != f)continue;
		bool ok = 1;
		int t = (a[0] < a[1]);
		
		//for(int i : a)cout << i << ' ';
		//cout << '\n';
		//cout << t << ' ';
		for(int i = 2; i < n; i ++ ) {
			int nt = (a[i-1] < a[i]);
			if(t == nt)ok = 0;
			t = nt;
			//cout << t << ' ';
		}
		//cout << '\n';
		//cout << '\n';
		ans = (ans + ok) %mod;
		
	}while(next_permutation(a.begin(), a.end()));
	
	cout << ans << '\n';
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

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