QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460196#5532. Kangaroofryan0 8ms138396kbC++202.3kb2024-07-01 05:57:042024-07-01 05:57:04

Judging History

你现在查看的是最新测评结果

  • [2024-07-01 05:57:04]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:138396kb
  • [2024-07-01 05:57:04]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 205;
const int mod = 1e9+7;

int n, cs, cf;
int dp[2][mxn][mxn][mxn];
int ans = 0;

signed main() {
	
	scanf("%lld%lld%lld", &n, &cs, &cf);
	memset(dp, 0, sizeof(dp));
	if (cs > cf) swap(cs,cf);
	dp[0][cs-1][cf-cs-1][n-cf] = 1;
	dp[1][cs-1][cf-cs-1][n-cf] = 1;
	
	for (int rem = n; rem >= 0; rem--) {
		for (int a1 = 0; a1 < n; a1++) {
			for (int a2 = 0; a2 < n; a2++) {
				int dir, a3;
				//dir = 0 : away
				dir = 0;
				if (rem-a1-a2 >= 0)  {
					a3 = rem-a1-a2;
					if (a1) {
						for (int na1 = 0; na1 < a1; na1++) {
							int na2 = a1-na1-1+a2;
							dp[1][na1][na2][a3] += dp[dir][a1][a2][a3];
							dp[1][na1][na2][a3] %= mod;
						}
					}
				}
				//dir = 1 : towards
				dir = 1;
				if (rem-a1-a2 >= 0) {
					a3 = rem-a1-a2;
					//case 1 - before
					if (a2) {
						for (int na2 = 0; na2 < a2; na2++) {
							int na1 = a1+a2-na2-1;
							dp[0][na1][na2][a3] += dp[dir][a1][a2][a3];
							dp[0][na1][na2][a3] %= mod;
						}
						
//						dp[0][a1][a2-1][a3] += dp[dir][a1][a2][a3];
//						dp[0][a1][a2-1][a3] %= mod;
					}
					//case 2 - after
					for (int na2 = 0; na2 < a3; na2++) {
						int na1 = a3-na2-1;
						int na3 = a1+a2;
						dp[1][na1][na2][na3] += dp[dir][a1][a2][a3];
						dp[1][na1][na2][na3] %= mod;
					}
				}
				if (rem == 0 && rem-a1-a2 >= 0) {
					a3 = rem-a1-a2;
					ans += dp[1][a1][a2][a3];
				}
				if (rem-a1-a2 >= 0) {
					int a3 = rem-a1-a2;
					if (dp[0][a1][a2][a3]) {
						printf("0 %d %d %d : %d\n", a1,a2,a3,dp[0][a1][a2][a3]);
					}
					if (dp[1][a1][a2][a3]) {
						printf("1 %d %d %d : %d\n", a1,a2,a3,dp[1][a1][a2][a3]);
					}
				}
	
			}
		}
	}
	
	printf("%lld", ans);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 138396kb

input:

7 3 6

output:

0 2 2 1 : 1
1 2 2 1 : 1
1 0 0 4 : 1
1 0 3 1 : 1
1 1 2 1 : 1
0 2 1 1 : 1
0 3 0 1 : 1
1 0 0 3 : 2
0 0 2 1 : 1
1 0 2 1 : 2
1 0 3 0 : 1
0 1 1 1 : 2
1 1 1 1 : 2
1 1 2 0 : 1
0 2 0 1 : 2
1 2 0 1 : 1
1 2 1 0 : 1
1 3 0 0 : 1
1 0 0 2 : 5
0 0 1 1 : 2
1 0 1 1 : 4
0 0 2 0 : 1
1 0 2 0 : 2
0 1 0 1 : 4
1 1 0 1 : 2
...

result:

wrong answer 1st numbers differ - expected: '14', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%