Submission #604424

#	Time	Username	Problem	Language	Result	Execution time	Memory
604424		Monchito	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	596 KiB

kangaroo

//-Si puedes imaginarlo, puedes programarlo- Alejandro Taboada
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)x.size()
#define rep(i,x,n) for(__typeof(n)i=(x);i!=(n);i+=1-2*((x)>(n)))
#define dbg(x) cout << #x << "=" << x << " ";
#define line cout << "\n.......................................................\n";

const int MOD = 1e9+7;

int n, cs, cf, dp[10][1<<10][3];

int solve(int pos, int msk, int dir){
	if(pos==cf) return __builtin_popcount(msk) == n-1;

	msk |= 1<<pos;
	int& ret=dp[pos][msk][dir];
	if(ret!=-1) return ret;

	ret=0;
	if(dir == 2){
		rep(i,0,n) if(!(msk & (1<<i))){
			ret += solve(i, msk, i < pos);
			ret %= MOD;
		}
	}
	else if(dir == 1){
		rep(i,pos+1,n) if(!(msk & (1<<i))){
			ret += solve(i, msk, 0);	
			ret %= MOD;
		}
	}
	else{
		rep(i,pos-1,-1) if(!(msk & (1<<i))){
			ret += solve(i, msk, 1);	
			ret %= MOD;
		}
	}
	return ret;
}

int main(){
	scanf("%d%d%d",&n,&cs,&cf);
	cs--, cf--;
	memset(dp,-1,sizeof(dp));
	printf("%d\n", solve(cs,0,2));
	return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d%d",&n,&cs,&cf);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~

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