QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#166846 | #1261. Inv | ucup-team1600# | AC ✓ | 98ms | 133920kb | C++20 | 3.8kb | 2023-09-06 19:20:18 | 2023-09-06 19:20:19 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
inline bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
inline bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL
const int max_n = 511, inf = 1000111222;
bool dp[max_n][max_n * max_n / 2] = {};
bool pref[max_n][max_n * max_n / 2] = {};
//inline int solve (int n, int k) {
// if (k > n * (n - 1) / 2) {
// return 0;
// }
// if (k < 0 || n < 0) {
// return 0;
// }
// if (n == 0 && k > 0) {
// return 0;
// }
// if (n == 0 && k == 0) {
// return 1;
// }
// LOG(n, k);
// if (calc[n][k]) {
// return dp[n][k];
// }
// calc[n][k] = true;
// dp[n][k] = solve(n - 1, k);
// for (int i = 1; i < n; i++) {
// dp[n][k] ^= solve(n - 2, k - (n - i + n - i - 1));
// }
// return dp[n][k];
//}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j <= k; j++) {
// solve(i, j);
//// cout << solve(i, j) << ' ';
// }
//// cout << '\n';
// }
dp[0][0] = 1;
pref[0][0] = 1;
for (int j = 0; j <= n * (n - 1) / 2; j += 2) {
pref[0][j] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n * (n - 1) / 2; j++) {
dp[i][j] = dp[i - 1][j];
if (i >= 2) {
int st = j - (i - (i - 1) + i - (i - 1) - 1);
if (st >= 0) {
dp[i][j] ^= pref[i - 2][st];
int l = j - (i - (1) + i - (1) - 1);
if (l - 2 >= 0) {
dp[i][j] ^= pref[i - 2][l - 2];
}
}
// for (int k = i - 1; k > 0 && j - (i - k + i - k - 1) >= 0; k--) {
// dp[i][j] ^= dp[i - 2][j - (i - k + i - k - 1)];
// }
}
pref[i][j] = dp[i][j];
if (j >= 2) {
pref[i][j] ^= pref[i][j - 2];
}
}
}
cout << dp[n][k] << '\n';
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j <= k; j++) {
// cout << dp[i][j] << ' ';
// }
// cout << '\n';
// }
// for (int i = 1; i <= n; i++) {
//
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 9780kb
input:
4 1
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7844kb
input:
10 21
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 98ms
memory: 132668kb
input:
500 124331
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9872kb
input:
20 122
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 3ms
memory: 32364kb
input:
100 999
output:
0
result:
ok answer is '0'
Test #6:
score: 0
Accepted
time: 90ms
memory: 133544kb
input:
500 100001
output:
1
result:
ok answer is '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7756kb
input:
5 0
output:
1
result:
ok answer is '1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
5 1
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
5 2
output:
1
result:
ok answer is '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
5 3
output:
1
result:
ok answer is '1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
5 4
output:
0
result:
ok answer is '0'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
5 5
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
5 6
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 5772kb
input:
5 7
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
5 8
output:
1
result:
ok answer is '1'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
5 9
output:
0
result:
ok answer is '0'
Test #17:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
5 10
output:
1
result:
ok answer is '1'
Test #18:
score: 0
Accepted
time: 94ms
memory: 133920kb
input:
500 73732
output:
1
result:
ok answer is '1'
Test #19:
score: 0
Accepted
time: 93ms
memory: 132772kb
input:
499 21121
output:
1
result:
ok answer is '1'
Test #20:
score: 0
Accepted
time: 88ms
memory: 132576kb
input:
499 100000
output:
0
result:
ok answer is '0'
Test #21:
score: 0
Accepted
time: 94ms
memory: 132504kb
input:
499 62262
output:
1
result:
ok answer is '1'
Test #22:
score: 0
Accepted
time: 88ms
memory: 133660kb
input:
499 23432
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 89ms
memory: 133452kb
input:
500 12321
output:
0
result:
ok answer is '0'
Test #24:
score: 0
Accepted
time: 91ms
memory: 132584kb
input:
500 60000
output:
1
result:
ok answer is '1'
Test #25:
score: 0
Accepted
time: 89ms
memory: 132312kb
input:
498 7498
output:
1
result:
ok answer is '1'
Test #26:
score: 0
Accepted
time: 87ms
memory: 133688kb
input:
498 76111
output:
1
result:
ok answer is '1'
Test #27:
score: 0
Accepted
time: 58ms
memory: 111244kb
input:
414 41414
output:
1
result:
ok answer is '1'
Test #28:
score: 0
Accepted
time: 55ms
memory: 112836kb
input:
422 42224
output:
1
result:
ok answer is '1'
Test #29:
score: 0
Accepted
time: 23ms
memory: 91720kb
input:
333 33333
output:
1
result:
ok answer is '1'
Test #30:
score: 0
Accepted
time: 90ms
memory: 132700kb
input:
500 51515
output:
1
result:
ok answer is '1'
Test #31:
score: 0
Accepted
time: 43ms
memory: 108468kb
input:
393 21222
output:
1
result:
ok answer is '1'
Test #32:
score: 0
Accepted
time: 96ms
memory: 133252kb
input:
500 124750
output:
1
result:
ok answer is '1'
Test #33:
score: 0
Accepted
time: 91ms
memory: 132784kb
input:
500 124749
output:
1
result:
ok answer is '1'
Test #34:
score: 0
Accepted
time: 98ms
memory: 133916kb
input:
500 0
output:
1
result:
ok answer is '1'
Test #35:
score: 0
Accepted
time: 95ms
memory: 132640kb
input:
500 1
output:
1
result:
ok answer is '1'
Test #36:
score: 0
Accepted
time: 2ms
memory: 5636kb
input:
1 0
output:
1
result:
ok answer is '1'