#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
int ones(int x){
int s = 0;
while(x > 0){
s+= (x%3==1);
x/= 3;
}
return s;
}
int all[1<<20];
main(){
int n;
cin >> n;
vector<int> a(n), binary(n), ternary(n);
for(int i = 0;i < n; i++){
cin >> a[i];
binary[i] = __builtin_popcount(a[i]);
ternary[i] = ones(a[i]);
// cout << binary[i] << ' ' << ternary[i] << '\n';
}
int answer = 0;
vector<int> b_used(1<<20, 0), t_used(1<<20, 0);
for(int mask = 0; mask < (1<< n); mask++){
set<int> st, st1, st2;
int B = 0, T = 0;
for(int i = 0;i < n; i++){
if(mask & (1<<i)){
st1.insert(binary[i]);
B+= (1<<i);
st.insert(binary[i]);
}else{
T+= (1<<i);
st2.insert(ternary[i]);
st.insert(ternary[i]);
}
}
if(st.size() == 1 && all[mask]==0){
all[mask] = 1;
answer++;
}
if(st1.size() == 1 and b_used[B]==0 and __builtin_popcount(B) > 1){
// cout << "binary ";
// for(int i = 0;i < n; i++){
// if(mask & (1<<i)){
// cout << a[i] << ' ';
// }
// }
// cout << '\n';
b_used[B] = 1;
answer++;
}
if(st2.size() == 1 and t_used[T]==0 and __builtin_popcount(T) > 1){
// cout << "ternary ";
// for(int i = 0;i < n; i++){
// if(mask & (1<<i)){
//
// }else{
// cout << a[i] << ' ';
// }
// }
// cout << '\n';
answer++;
t_used[T] = 1;
}
}
cout << answer;
return 0;
}
Compilation message
beauty.cpp:19:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
19 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
16724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
