Submission #110841

#	Time	Username	Problem	Language	Result	Execution time	Memory
110841		Nicholas_Patrick	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	98 ms	21240 KiB

kangaroo

#include <cstdio>
#include <vector>
#define llc (long long)
#define pm %1000000007
using namespace std;

int memo[2001][1001][3];
int n, s, e;
bool valid(int i, int j, int k){
	if(i<0||i>n)return false;
	if(j<0||j>((n+1)>>1))return false;
	if(k<0||k>2)return false;
	if(j>i)return false;
	// if(i!=n&&k>j)return false;
	// if(k>i&&n!=1)return false;// won't happen
	return true;
}
int main(){
	//obvious goal: find # of perm [0, n) such that tracing 0-1-2 -> zig zag, arr[s]=0, arr[e]=n-1
	//inverted goal: find # of perm [0, n) such that value goes up and down, arr[0]=s, arr[n-1]=e
	//in inverted goal, k can only increase when value to add is s or e, rest: stick to slide
	//honestly, I don't fully understand why the algorithm described in the slide works more practice needed


	scanf("%d%d%d", &n, &s, &e);s--;e--;
	//pertama kalinya aku pakai %d tanpa spasi
	//kelihatannya lebih aman, jadi akan selamanya
	//aku pakai ini kecuali ternyata aku salah
	memo[0][0][0]=1;
	for(int i = 0;i < n;i ++){
		for(int j = 0;j <= (n+1)>>1 && j <= i;j ++){
			for(int k = 0;k <= 2 && k <= j;k ++){
				if(i!=s&&i!=e){//k may not increase
					if(valid(i+1, j+1, k)){//new cc
						memo[i+1][j+1][k]=(memo[i+1][j+1][k]+llc memo[i][j][k]*(j+1-k)) pm;
					}
					//apparently, this step is not needed, it just works on paper :P
					// if(valid(i+1, j, k)){//stick to cc
					// 	memo[i+1][j][k]=(memo[i+1][j][k]+llc memo[i][j][k]*((j<<1)-k)) pm;
					// }
					if(valid(i+1, j-1, k)){//merge cc
						memo[i+1][j-1][k]=(memo[i+1][j-1][k]+llc memo[i][j][k]*(j-1)) pm;
					}
				}else{//k may increase
					if(valid(i+1, j, k+1)){
						memo[i+1][j][k+1]=(memo[i+1][j][k+1]+memo[i][j][k]) pm;
					}
					if(valid(i+1, j+1, k+1)){
						memo[i+1][j+1][k+1]=(memo[i+1][j+1][k+1]+memo[i][j][k]) pm;
					}
				}
			}
		}
	}
	// for(int i = 0;i <= n;i ++){
	// 	for(int j = 0;j <= (n+1)>>1;j ++){
	// 		for(int k = 0;k <= 2;k ++){
	// 			printf("%d ", memo[i][j][k]);
	// 		}
	// 		printf("\n");
	// 	}
	// 	printf("\n");
	// }
	printf("%d\n", memo[n][1][2]);
}

Compilation message (stderr)

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

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