QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #320731 | #8174. Set Construction | ucup-team1600 | TL | 372ms | 14272kb | C++20 | 9.6kb | 2024-02-03 20:43:09 | 2024-02-03 20:43:10 |
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}] = {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);
LOG(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: 345ms
memory: 14076kb
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: 0
Accepted
time: 366ms
memory: 14272kb
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 7 11 15 63 0 1 3 7 11 15 31 63 0 1 2 3 7 11 15 31 63 0 1 2 3 6 7 15 23 31 63 0 1 2 3 4 5 6 7 15 31 63 0 1 2 3 4 5 6 7 15 31 47 63 0 1 2 3 6 7 14 15 22 23 30 31 63 0 1 3 4 5 7 8 9 11 12 13 15 31 63 0 1 2 3 4 5 6 7 15 23 31 39 47 55 63 0...
result:
ok AC
Test #3:
score: 0
Accepted
time: 366ms
memory: 14108kb
input:
30 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 7 20 7 21 7 22 7 23 7 24 7 25 7 26 7 27 7 28 8 2 8 3 8 4 8 5 8 6 8 7 8 8 8 9 8 10 8 11 8 12 8 13 8 14
output:
0 1 3 7 11 15 19 23 27 31 63 127 0 1 3 7 11 15 31 47 63 79 95 111 127 0 1 2 3 7 11 15 31 47 63 79 95 111 127 0 1 3 7 15 31 39 47 63 71 79 95 103 111 127 0 1 2 3 4 5 6 7 15 31 47 63 79 95 111 127 0 1 2 3 6 7 15 31 39 47 63 71 79 95 103 111 127 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 31 127 0 1 3...
result:
ok AC
Test #4:
score: 0
Accepted
time: 371ms
memory: 14040kb
input:
30 8 15 8 16 8 17 8 18 8 19 8 20 8 21 8 22 8 23 8 24 8 25 8 26 8 27 8 28 8 29 8 30 8 31 8 32 8 33 8 34 8 35 8 36 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9
output:
0 1 2 3 7 15 23 31 63 95 127 159 191 223 255 0 1 2 3 4 5 6 7 14 15 31 47 63 127 191 255 0 1 2 3 4 5 6 7 15 23 31 39 47 55 63 127 255 0 1 2 3 4 5 6 7 15 23 31 63 95 127 159 191 223 255 0 1 2 3 7 8 9 10 11 15 24 25 26 27 31 63 95 127 255 0 1 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 127 255 ...
result:
ok AC
Test #5:
score: 0
Accepted
time: 372ms
memory: 14080kb
input:
30 9 10 9 11 9 12 9 13 9 14 9 15 9 16 9 17 9 18 9 19 9 20 9 21 9 22 9 23 9 24 9 25 9 26 9 27 9 28 9 29 9 30 9 31 9 32 9 33 9 34 9 35 9 36 9 37 9 38 9 39
output:
0 1 3 7 15 31 47 63 127 511 0 1 3 7 15 31 63 127 191 255 511 0 1 3 7 11 15 31 63 127 191 255 511 0 1 2 3 7 11 15 31 63 127 191 255 511 0 1 2 3 7 15 23 31 63 95 127 255 383 511 0 1 3 7 11 15 31 47 63 79 95 111 127 255 511 0 1 2 3 7 11 15 31 47 63 79 95 111 127 255 511 0 1 2 3 4 5 6 7 15 23 31 ...
result:
ok AC
Test #6:
score: 0
Accepted
time: 357ms
memory: 14076kb
input:
6 9 40 9 41 9 42 9 43 9 44 9 45
output:
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 127 191 255 319 383 447 511 0 1 2 3 6 7 15 23 31 39 47 55 63 127 135 143 151 159 167 175 183 191 255 263 271 279 287 295 303 311 319 383 391 399 407 415 423 431 439 447 511 0 1 2 3 7 11 15 31 47 63 79 95 111 1...
result:
ok AC
Test #7:
score: -100
Time Limit Exceeded
input:
30 60 1801 60 1802 60 1803 60 1804 60 1805 60 1806 60 1807 60 1808 60 1809 60 1810 60 1811 60 1812 60 1813 60 1814 60 1815 60 1816 60 1817 60 1818 60 1819 60 1820 60 1821 60 1822 60 1823 60 1824 60 1825 60 1826 60 1827 60 1828 60 1829 60 1830
output:
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 15...