QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #320720 | #8174. Set Construction | ucup-team1600 | WA | 389ms | 13768kb | C++20 | 9.5kb | 2024-02-03 20:35:42 | 2024-02-03 20:35:43 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#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>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG 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 DEBUG while (false)
#define LOG(...)
#endif
const int max_n = -1, inf = 1000111222;
mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
return uniform_int_distribution<T>(l, r)(rng);
}
inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
return uniform_real_distribution<ld>(l, r)(rng);
}
set <ll> solution[10][1411];
inline void solve (int n) {
set <pii> can;
int ccc = 0;
while (ccc < 1000) {
++ccc;
set <ll> have = {0, (1ll << n) - 1};
queue <ll> q;
for (auto &i : have) {
q.push(i);
}
int cc = 0;
while (cc < 10) {
if (n * (n + 1) / 2 + 2 >= len(have)) {
if (!can.count({n, len(have)})) {
can.insert({n, len(have)});
solution[n][len(have)] = have;
}
}
int prv = len(have);
ll cur = randll(0ll, (1ll << n) - 1);
have.insert(cur);
q.push(cur);
while (!q.empty()) {
ll x = q.front();
q.pop();
set<ll> add;
for (auto &i: have) {
if (!have.count(i | x)) {
add.insert(i | x);
}
if (!have.count(i & x)) {
add.insert(i & x);
}
}
for (auto &i: add) {
have.insert(i);
q.push(i);
}
}
if (prv == len(have)) ++cc;
}
LOG(len(can), n * (n + 1) / 2 + 1);
if (n * (n + 1) / 2 + 1 == len(can)) {
break;
}
}
}
//
//inline void test_case (int N = -1, int MM = -1) {
// int n, m;
// if (N == -1) {
// cin >> n >> m;
// }
// else {
// n = N;
// m = MM;
// }
// int M = m;
// set <ll> have = {0, (1ll << n) - 1};
// m -= 2;
// ll now = 0;
// int num = 0;
//// vector <int> dp(m + 1, inf);
//// dp[0] = 0;
//// for (int i = 1; i < 20; i++) {
//// for (int j = 0; j + (1 << i) - 1 <= m; j++) {
//// umin(dp[j + (1 << i) - 1], dp[j] + i);
//// }
//// }
//// LOG(dp[m]);
// for (int i = 20; i >= 1 && (n - num > 9 || solution[max(0, n - num)][m + 2].empty()); i--) {
// while ((1ll << i) - 1 <= m) {
//// LOG(m, i, m - (1ll << i) + 1, (1ll << i) - 1, n - num);
// m -= (1ll << i) - 1;
// ll new_now = now;
// for (int j = 0; j < i; j++) {
// have.insert(now | (1ll << num));
// new_now |= 1ll << num;
// ++num;
// }
// now = new_now;
// }
// }
//
// if (m > 0 && !solution[n - num][m + 2].empty()) {
//// LOG(len(solution[n - num][m + 2]));
// if (solution[n - num][m + 2].empty()) {
// LOG("here");
// }
// for (ll x : solution[n - num][m + 2]) {
// ll X = x << num;
// have.insert(X | now);
// }
// }
// else {
//
// }
//
//// LOG(m, num);
// queue <ll> q;
// for (auto &i : have) {
// q.push(i);
// }
// while (!q.empty()) {
// ll x = q.front();
// q.pop();
// set <ll> add;
// for (auto &i : have) {
// if (!have.count(i | x)) {
// add.insert(i | x);
// }
// if (!have.count(i & x)) {
// add.insert(i & x);
// }
// }
// for (auto &i : add) {
// have.insert(i);
// q.push(i);
// }
// }
//// LOG(len(have), M);
//// for (auto &i : have) cout << i << ' ';
//// cout << '\n';
// if (len(have) != M) {
// LOG(n, M, abs(len(have) - M), num);
// }
//}
map <pii, pair<pii, pii> > gg;
set <pii> h;
inline void gen () {
queue <pii> q;
for (int i = 1; i < 20; i++) {
int cnt = (1 << i);
if (cnt > 1830) {
break;
}
h.insert({i, cnt});
q.push({i, cnt});
}
int cc = 0;
while (!q.empty()) {
++cc;
// LOG(len(have));
pii x = q.front();
q.pop();
set <pii> add;
for (auto &i : h) {
if (i.first + x.first <= 60) {
if (i.second + x.second - 1 <= 1830) {
if (!h.count({i.first + x.first, i.second + x.second - 1})) {
add.insert({i.first + x.first, i.second + x.second - 1});
gg[{i.first + x.first, i.second + x.second - 1}] = {x, i};
}
}
if (i.second * x.second <= 1830) {
if (!h.count({i.first + x.first, i.second * x.second})) {
add.insert({i.first + x.first, i.second * x.second});
gg[{i.first + x.first, i.second + x.second - 1}] = {x, i};
}
}
}
else {
break;
}
}
for (auto &i : add) {
q.push(i);
h.insert(i);
}
if (cc > 49) {
LOG(cc);
bool ok = true;
for (int i = 2; i <= 60; i++) {
set<int> now = {2};
int mx = i * (i + 1) / 2;
for (auto &j: h) {
if (j.second > mx) {
continue;
}
if (j.first < i && j.second + 1 <= mx) {
now.insert(j.second + 1);
}
if (j.first == i) {
now.insert(j.second);
}
}
now.erase(1);
now.erase(0);
if (len(now) != mx - 1 && i != 4) {
ok = false;
}
LOG(len(now), mx - 1);
}
if (ok) {
LOG("done");
return;
}
}
}
}
inline set<ll> rec (int n, int m) {
set <ll> have;
if (gg.count({n, m})) {
pii x, y;
tie(x, y) = gg[{n, m}];
auto l = rec(x.first, x.second);
auto r = rec(y.first, y.second);
have = r;
if (x.second * y.second == m) {
for (auto &i : l) {
have.insert(i << y.first);
}
}
else {
for (auto &i : l) {
have.insert((i << y.first) | ((1ll << y.first) - 1));
}
}
}
else {
for (int i = 0; i < n; i++) {
have.insert(1 << i);
}
}
return have;
}
inline void test_case () {
int n, m;
cin >> n >> m;
if (m == 2) {
cout << "0 " << (1ll << n) - 1 << '\n';
return;
}
if (n == 4) {
for (auto &i : solution[n][m]) {
cout << i << ' ';
}
cout << '\n';
return;
}
int N = n, M = m;
for (auto &i : h) {
if (i.first < n && i.second + 1 == m) {
N = i.first;
M = i.second;
}
if (i.first == n && i.second == m) {
N = i.first;
M = i.second;
}
}
int num = 0;
auto have = rec(N, M);
have.insert(0);
have.insert((1ll << n) - 1);
queue <ll> q;
for (auto &i : have) {
q.push(i);
}
while (!q.empty()) {
ll x = q.front();
q.pop();
set <ll> add;
for (auto &i : have) {
if (!have.count(i | x)) {
add.insert(i | x);
}
if (!have.count(i & x)) {
add.insert(i & x);
}
}
for (auto &i : add) {
have.insert(i);
q.push(i);
}
}
// assert(len(have) == m);
for (auto &i : have) {
cout << i << ' ';
}
cout << '\n';
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
solve(4);
gen();
// return 0;
// for (int i = 2; i <= 9; i++) {
// solve(i);
// }
//// test_case(33, 506);
//// return 0;
// for (int i = 2; i <= 60; i++) {
// for (int j = 2; j <= i * (i + 1) / 2; j++) {
// test_case(i, j);
// }
// }
int t = 1;
cin >> t;
for (int test = 1; test <= t; test++) {
test_case();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 368ms
memory: 13616kb
input:
3 3 5 4 8 60 2
output:
0 1 2 3 7 0 2 4 6 10 11 14 15 0 1152921504606846975
result:
ok AC
Test #2:
score: -100
Wrong Answer
time: 389ms
memory: 13768kb
input:
30 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 6 20 6 21 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11
output:
0 63 0 1 63 0 1 3 63 0 1 3 7 63 0 1 3 7 15 63 0 1 3 5 7 15 63 0 1 3 7 15 23 31 63 0 1 3 7 11 15 31 47 63 0 1 2 3 7 11 15 31 47 63 0 1 2 3 4 5 6 7 15 31 63 0 1 3 5 7 9 11 13 15 31 47 63 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 63 0 1 2 3 4 5 6 7...
result:
wrong answer 63 is not in A