Submission #473811

#	Time	Username	Problem	Language	Result	Execution time	Memory
473811		Prabhakar_987	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	41 ms	31692 KiB

kangaroo

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

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

string to_string(char c) {
	return string(1, c);
}
string to_string(string s) {
	return s;
}
string to_string(const char* s) {
	return string(s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
	string res;
	for(int i = 0; i < (int)v.size(); i++)
		res+=char('0'+v[i]);
	return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #VA_ARGS << "]:", debug_out(VA_ARGS)
#else
#define debug(...) 42
#endif

#define FOR(i,a,b)      for (int i = (a); i < (b); ++i)
#define F0R(i,a)        FOR(i,0,a)
#define ROF(i,a,b)      for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a)        ROF(i,0,a)
#define rep(a)          F0R(_,a)
#define IOS             ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define dbg(x)          cout << #x << "=" << x << endl
#define dbg2(x, y)      cout << #x << "=" << x << "," << #y << "=" << y << endl
#define dbg3(x, y,z)    cout << #x << "=" << x << "," << #y << "=" << y <<"," << #z << "=" << z << endl
#define ff              first
#define ss              second
#define all(x)          (x).begin(), (x).end()
#define pb              push_back
#define mp              make_pair
#define sz(x)           (int)(x).size()
#define lb              lower_bound
#define ub              upper_bound 
#define endl            "\n"
#define mem0(a)         memset(a,0,sizeof(a))
#define mem1(a)         memset(a,-1,sizeof(a))
#define memf(a)         memset(a,false,sizeof(a))
#define memt(a)         memset(a,true,sizeof(a))
#define meminf(a)       memset(a,0x7f,sizeof(a))
#define nO              {cout<<"NO\n"; return;}
#define yES             {cout<<"YES\n"; return;}
#define neg             {cout<<"-1\n"; return;}
#define each(a,x)       for (auto& a: x)
#define ar              array
mt19937_64 				      rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define int             long long

template<typename T> using V = vector<T>;
template<typename T> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<typename T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

 
using ll = long long;
using db = long double;
using vd = vector<db>; 
using vs = vector<string>;
using pi = pair<int,int>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;

template<class A> void read(V<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(V<A>& x) {
	each(a, x)
		read(a);
}
template<class A, size_t S> void read(ar<A, S>& x) {
	each(a, x)
		read(a);
}

const int mod = 1000000007;
const ll INF = 1e18;
const db PI = acos((db)-1);

// bitwise ops
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
	return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

void add(int &a, int b){
  a += b;
  if(a >= mod) a -= mod;
}

int mul(int a, int b){
  return a * b % mod;
}

void solve(){
  int n; cin >> n;
  int x,y;
  cin >> x >> y;
  int a = min(x,y);
  int b = max(x,y);
  vector<vi> dp(n+2,vi(n+2,0));
  dp[0][0] = 1;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      if(i == x || i == y){
        add(dp[i][j], dp[i-1][j-1]);
        add(dp[i][j], dp[i-1][j]);
      }
      else{
        add(dp[i][j], mul(dp[i-1][j+1], j));
        if(i < a) add(dp[i][j], mul(dp[i-1][j-1], j));
        else if(i > a && i < b) add(dp[i][j], mul(dp[i-1][j-1], j-1));
        else add(dp[i][j], mul(dp[i-1][j-1], j-2));
      }
    }
  }
  cout << dp[n][1] << endl;
}

signed main(){
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  IOS;
  int tt = 1;
  //cin >> tt;
  for(int ii = 1; ii <= tt; ii++)
    solve();
}

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