Submission #485641

#	Time	Username	Problem	Language	Result	Execution time	Memory
485641		inluminas	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	0 ms	204 KiB

kangaroo

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=2e3+1;
const ll mod=1e9+7;
int n,cf,cs;
bool state[lmt];
ll ans;

ll f(ll cnt){
  if(!cnt) return 1LL;
  ll res=1;
  for(int i=1;i<=cnt;i++) res=(res*i)%mod;
  return res;
}

void solve(){
  for(int i=2;i<=n;i++) state[i]=state[i-1]^1;
  ll o=0,z=0;
  for(int i=3;i<n-1;i++){
    if(state[i]) o++;
    else z++;
  }
  ll stan=(f(o)*f(z))%mod;
  vector<int>left;
  for(int i=1;i<=n;i++){
    if(i==cs || i==cf) continue;
    left.push_back(i);
  }
  bool status[n+1];
  memset(status,0,sizeof status);
  o=0,z=0;
  for(int i=2;i<n;i++){
    if(state[i]) o++;
    else z++;
  }
  while(!left.empty()){
    if(o){
      status[left.back()]=1;
      o--;
    }else status[left.back()]=0;
    left.pop_back();
  }
  ll res=0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(i==cf || i==cs || j==cf || j==cs) continue;
      if((i>cs)!=state[2]) continue;
      if((j>cf)!=state[n-1]) continue;
      if((2==n-1)!=(i==j)) continue;
      if(status[i]!=state[2] || status[j]!=state[n-1]) continue;
      res=(res+stan)%mod;
      //cout<<res<<" "<<i<<" "<<j<<endl;
    }
  }
  ans=(ans+res)%mod;
  //cout<<res<<endl;
  return;
}

int main(){
  fastio;

  cin>>n>>cs>>cf;
  if(n==2){
    cout<<1<<endl;
    return 0;
  }
  state[1]=0;
  solve();
  state[1]=1;
  solve();
  cout<<ans<<endl;
  return 0;
}

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