oj.uz

Submission #49257

# Submission time Handle Problem Language Result Execution time Memory
49257 2018-05-24T14:16:45 Z Sherlock221b Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 864 ms 130064 KB 
#include <bits/stdc++.h>
 
 
#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define MOD(x,y) (((x)*(y))%mod)
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,cur) N=(N|(1LL<<cur))
#define Reset(N,cur) N=(N&(~(1LL<<cur)))
#define Check(N,cur) (!((N&(1LL<<cur))==0))
#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
#define dump(x) cerr<<"~ "<<#x<<" = "<<x<<endl
//Imran addition
#define rep(i,n) for(int i = 1; i <= n; i++)
#define mem CLR
#define pf printf
#define sc scanf
#define endl "\n"
#define gi(k) scanf("%d",&k)
#define gl(k) scanf("%lld",&k)
#define NMAX 2147483647
#define LMAX 9223372036854775807LL
 
using namespace std;
 
 
#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<int> vi;
typedef vector<vlong> vl;
typedef vector<pll> vll;
 
inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}
 
 
const vlong inf = 2147383647;
const vlong mod = 1000000007;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

vlong dp[202][202][202];
 

vlong f(int lf, int ri, int tri, int flag) {
	vlong &res = dp[lf][ri][tri];

	if(res != -1) return res;

	if(lf + ri == 1) {
		//pf("DD %d %d\n",ri,tri);
		return res = lf ^ flag; //ri ^ flag
	}

	res = 0;
	int dir;

	if((lf+ri) & 1) dir = flag;
	else dir = flag ^ 1; 

	if(!dir) { //going to left

		if(ri < tri) { //current is right of target
			int x = tri - ri;

			for(int i = 1; i < x; i++) {
				res = (res + f(lf-i, ri+i-1, tri-1, flag)) % mod;
			}

			for(int i = x+1; i <= lf; i++) {
				res = (res + f(lf-i, ri+i-1, tri, flag)) % mod;
			}
		}


		else {
			for(int i = 1; i <= lf; i++) {
				res = (res + f(lf-i, ri+i-1, tri, flag)) % mod;
			}
		}

	}

	else {	//going to right

		if(ri < tri) {
			for(int i = 1; i <= ri; i++) {
				res = (res + f(lf+i-1, ri-i, tri-1, flag)) % mod;
			}
		}

		else {
			int x = ri-tri+1;

			for(int i = 1; i < x; i++) {
				res = (res + f(lf+i-1, ri-i, tri, flag)) % mod;
			}

			for(int i = x+1; i <= ri; i++) {
				res = (res + f(lf+i-1, ri-i, tri-1, flag)) % mod;
			}
		}
	}


	return res;
}
 
 
int main () {
 
 	#ifdef forthright48
    freopen ( "00_input.txt", "r", stdin ); //freopen ( "00_output.txt", "w", stdout );
 	#endif

 	int n,a,b,x,y,z;
 	vlong ans;
 
    cin >> n >> a >> b;

    x = a-1; y = n-a; z = n-b+1;
    if(a > b) z--;

    mem(dp,-1);
    ans = f(x,y,z,0);
	
	mem(dp,-1);
	ans = (ans + f(x,y,z,1)) % mod;

	cout << ans << endl;
 
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 64760 KB Output is correct
2 Correct 69 ms 64868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 64760 KB Output is correct
2 Correct 69 ms 64868 KB Output is correct
3 Correct 69 ms 64944 KB Output is correct
4 Correct 75 ms 65148 KB Output is correct
5 Correct 71 ms 65148 KB Output is correct
6 Correct 68 ms 65240 KB Output is correct
7 Correct 75 ms 65240 KB Output is correct
8 Correct 62 ms 65240 KB Output is correct
9 Correct 61 ms 65240 KB Output is correct
10 Correct 64 ms 65240 KB Output is correct
11 Correct 69 ms 65240 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 64760 KB Output is correct
2 Correct 69 ms 64868 KB Output is correct
3 Correct 69 ms 64944 KB Output is correct
4 Correct 75 ms 65148 KB Output is correct
5 Correct 71 ms 65148 KB Output is correct
6 Correct 68 ms 65240 KB Output is correct
7 Correct 75 ms 65240 KB Output is correct
8 Correct 62 ms 65240 KB Output is correct
9 Correct 61 ms 65240 KB Output is correct
10 Correct 64 ms 65240 KB Output is correct
11 Correct 69 ms 65240 KB Output is correct
12 Correct 741 ms 65256 KB Output is correct
13 Correct 531 ms 65256 KB Output is correct
14 Correct 110 ms 65260 KB Output is correct
15 Correct 793 ms 65272 KB Output is correct
16 Correct 116 ms 65384 KB Output is correct
17 Correct 864 ms 65408 KB Output is correct
18 Correct 219 ms 65408 KB Output is correct
19 Correct 754 ms 65408 KB Output is correct
20 Correct 839 ms 65408 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 64760 KB Output is correct
2 Correct 69 ms 64868 KB Output is correct
3 Correct 69 ms 64944 KB Output is correct
4 Correct 75 ms 65148 KB Output is correct
5 Correct 71 ms 65148 KB Output is correct
6 Correct 68 ms 65240 KB Output is correct
7 Correct 75 ms 65240 KB Output is correct
8 Correct 62 ms 65240 KB Output is correct
9 Correct 61 ms 65240 KB Output is correct
10 Correct 64 ms 65240 KB Output is correct
11 Correct 69 ms 65240 KB Output is correct
12 Correct 741 ms 65256 KB Output is correct
13 Correct 531 ms 65256 KB Output is correct
14 Correct 110 ms 65260 KB Output is correct
15 Correct 793 ms 65272 KB Output is correct
16 Correct 116 ms 65384 KB Output is correct
17 Correct 864 ms 65408 KB Output is correct
18 Correct 219 ms 65408 KB Output is correct
19 Correct 754 ms 65408 KB Output is correct
20 Correct 839 ms 65408 KB Output is correct
21 Runtime error 120 ms 130064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -