QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#49488 | #1261. Inv | ckiseki# | AC ✓ | 223ms | 90028kb | C++ | 2.4kb | 2022-09-21 16:53:38 | 2022-09-21 16:53:39 |
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];
}
}
auto brute(int n) {
vector<int> p(n, -1);
vector<int> res(n * (n-1) / 2 + 1);
const auto dfs = [&](auto self, int i) {
if (i == n) {
int cnt = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < x; y++) {
if (p[y] > p[x])
++cnt;
}
}
// cerr << "cnt = " << cnt << endl;
// for (int x = 0; x < n; x++)
// cerr << p[x]+1 << ' ';
// cerr << endl;
++res[cnt];
return;
}
if (p[i] != -1) {
self(self, i + 1);
return;
}
p[i] = i;
self(self, i + 1);
p[i] = -1;
for (int j = i + 1; j < n; j++) {
if (p[j] != -1) continue;
p[i] = j;
p[j] = i;
self(self, i + 1);
p[i] = p[j] = -1;
}
};
dfs(dfs, 0);
for (int i = 0; i <= n*(n-1)/2; i++) {
cout << res[i] << ' ';
}
cout << '\n';
return res;
}
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];
if (i>=2) {
build(i-2);
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 - (i-2-k)*2 - 1;
// if (jj >= 0)
// dp[i][j] += dp[i-2][jj];
// }
}
}
}
// cout << dp[n][K] << '\n';
cout << dp[n][K] % 2 << '\n';
// for (int j = 0; j <= n*(n-1)/2; j++) {
// cout << dp[n][j] << ' ';
// }
// cout << '\n';
// auto R = brute(n);
// for (int j = 0; j <= n*(n-1)/2; j++) {
// assert (dp[n][j] == R[j]);
// }
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4724kb
input:
4 1
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 4588kb
input:
10 21
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 213ms
memory: 87912kb
input:
500 124331
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 13ms
memory: 4700kb
input:
20 122
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 46ms
memory: 5704kb
input:
100 999
output:
0
result:
ok answer is '0'
Test #6:
score: 0
Accepted
time: 199ms
memory: 88000kb
input:
500 100001
output:
1
result:
ok answer is '1'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4636kb
input:
5 0
output:
1
result:
ok answer is '1'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4576kb
input:
5 1
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 4ms
memory: 4640kb
input:
5 2
output:
1
result:
ok answer is '1'
Test #10:
score: 0
Accepted
time: 5ms
memory: 4728kb
input:
5 3
output:
1
result:
ok answer is '1'
Test #11:
score: 0
Accepted
time: 5ms
memory: 4636kb
input:
5 4
output:
0
result:
ok answer is '0'
Test #12:
score: 0
Accepted
time: 5ms
memory: 4652kb
input:
5 5
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 2ms
memory: 4564kb
input:
5 6
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 2ms
memory: 4720kb
input:
5 7
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4576kb
input:
5 8
output:
1
result:
ok answer is '1'
Test #16:
score: 0
Accepted
time: 2ms
memory: 4508kb
input:
5 9
output:
0
result:
ok answer is '0'
Test #17:
score: 0
Accepted
time: 5ms
memory: 4576kb
input:
5 10
output:
1
result:
ok answer is '1'
Test #18:
score: 0
Accepted
time: 202ms
memory: 88012kb
input:
500 73732
output:
1
result:
ok answer is '1'
Test #19:
score: 0
Accepted
time: 192ms
memory: 87592kb
input:
499 21121
output:
1
result:
ok answer is '1'
Test #20:
score: 0
Accepted
time: 181ms
memory: 87592kb
input:
499 100000
output:
0
result:
ok answer is '0'
Test #21:
score: 0
Accepted
time: 170ms
memory: 87420kb
input:
499 62262
output:
1
result:
ok answer is '1'
Test #22:
score: 0
Accepted
time: 181ms
memory: 87420kb
input:
499 23432
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 201ms
memory: 87908kb
input:
500 12321
output:
0
result:
ok answer is '0'
Test #24:
score: 0
Accepted
time: 206ms
memory: 87992kb
input:
500 60000
output:
1
result:
ok answer is '1'
Test #25:
score: 0
Accepted
time: 205ms
memory: 88792kb
input:
498 7498
output:
1
result:
ok answer is '1'
Test #26:
score: 0
Accepted
time: 222ms
memory: 88992kb
input:
498 76111
output:
1
result:
ok answer is '1'
Test #27:
score: 0
Accepted
time: 129ms
memory: 54444kb
input:
414 41414
output:
1
result:
ok answer is '1'
Test #28:
score: 0
Accepted
time: 173ms
memory: 56552kb
input:
422 42224
output:
1
result:
ok answer is '1'
Test #29:
score: 0
Accepted
time: 143ms
memory: 31388kb
input:
333 33333
output:
1
result:
ok answer is '1'
Test #30:
score: 0
Accepted
time: 188ms
memory: 89952kb
input:
500 51515
output:
1
result:
ok answer is '1'
Test #31:
score: 0
Accepted
time: 158ms
memory: 47788kb
input:
393 21222
output:
1
result:
ok answer is '1'
Test #32:
score: 0
Accepted
time: 223ms
memory: 89440kb
input:
500 124750
output:
1
result:
ok answer is '1'
Test #33:
score: 0
Accepted
time: 186ms
memory: 89272kb
input:
500 124749
output:
1
result:
ok answer is '1'
Test #34:
score: 0
Accepted
time: 192ms
memory: 90028kb
input:
500 0
output:
1
result:
ok answer is '1'
Test #35:
score: 0
Accepted
time: 197ms
memory: 89968kb
input:
500 1
output:
1
result:
ok answer is '1'
Test #36:
score: 0
Accepted
time: 3ms
memory: 5688kb
input:
1 0
output:
1
result:
ok answer is '1'