QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#49486 | #1261. Inv | ckiseki# | WA | 215ms | 92024kb | C++ | 1.0kb | 2022-09-21 16:36:29 | 2022-09-21 16:36:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
uint32_t dp[maxn][maxn * maxn];
uint32_t pre[maxn * maxn];
void build(int x) {
for (int i = 0; i < maxn * maxn; i++) {
pre[i] = dp[x][i];
if (i >= 2) pre[i] += pre[i - 2];
}
}
uint32_t query(int r, int l) {
if (r < 0)
return 0;
else if (l - 2 < 0)
return pre[r];
else
return pre[r] - pre[l - 2];
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, K;
cin >> n >> K;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i*(i-1)/2; j++)
dp[i][j] = dp[i-1][j];
build(i-1);
for (int j = 0; j <= i*(i-1)/2; j++) {
dp[i][j] += query(j - 1, j - 1 - (i-2) * 2);
// for (int k = 0; k <= i-2; k++) {
// int jj = j - k*2 - 1;
// if (jj >= 0)
// dp[i][j] += dp[i-1][jj];
// }
}
}
// cout << dp[n][K] << '\n';
cout << dp[n][K] % 2 << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 10400kb
input:
4 1
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 7ms
memory: 10652kb
input:
10 21
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 215ms
memory: 90972kb
input:
500 124331
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 8728kb
input:
20 122
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 36ms
memory: 9704kb
input:
100 999
output:
0
result:
ok answer is '0'
Test #6:
score: -100
Wrong Answer
time: 163ms
memory: 92024kb
input:
500 100001
output:
0
result:
wrong answer expected '1', found '0'