QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351085 | #8174. Set Construction | ucup-team173 | WA | 1ms | 3928kb | C++20 | 2.4kb | 2024-03-11 15:06:31 | 2024-03-11 15:06:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))
typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
set<int> f(int n, int m) {
if(m <= n * (n - 1) / 2) {
auto s = f(n - 1, m);
set<int> st;
for(auto i : s) st.insert(i * 2);
return st;
} else if(n >= 3 && m % 2 == 0) {
auto s = f(n - 1, m / 2);
set<int> st;
for(auto i : s) {
st.insert(i * 2);
st.insert(i * 2 + 1);
}
return st;
} else if(n >= 6 && m % 2 == 1) {
auto s = f(n - 1, m - 1);
set<int> st; st.insert(0);
for(auto i : s) {
st.insert(2 * i + 1);
}
return st;
} else if(n == 5 && m == 15) {
auto s1 = f(2, 3), s2 = f(3, 5);
set<int> st;
for(auto i : s1) {
for(auto j : s2) {
st.insert(i * 8 + j);
}
}
return st;
} else {
vi a((1 << n) - 2);
for(int i = 0; i < m - 2; i++) a[i] = 1;
sort(a.begin(), a.end());
do {
vi vis(1 << n);
vis[0] = vis[(1 << n) - 1] = 1;
for(int i = 0; i < (1 << n) - 2; i++)
if(a[i]) vis[i + 1] = 1;
int fl = 1;
for(int i = 0; i < (1 << n); i++) if(vis[i])
for(int j = i; j < (1 << n); j++) if(vis[j]) {
if(!vis[i | j] || !vis[i & j]) {
fl = 0;
}
}
if(fl) {
set<int> st;
for(int i = 0; i < (1 << n); i++) if(vis[i]) st.insert(i);
return st;
}
} while(next_permutation(a.begin(), a.end()));
}
}
void solve() {
int n, m;
cin >> n >> m;
auto s = f(n, m);
for(auto i : s) cout << i << ' ';
cout << '\n';
}
signed main() {
atexit([](){cerr << "time: " << (db)clock()/CLOCKS_PER_SEC << "s\n";});
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3928kb
input:
3 3 5 4 8 60 2
output:
0 4 5 6 7 0 1 2 3 12 13 14 15 0
result:
wrong output format Unexpected end of file - int64 expected