/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
const int N = 35;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int n, m, k, ans;
vii a(N);
int cnt1(int x){
int cnt = 0;
while(x){
if(x%3 == 1) cnt++;
x/=3;
}return cnt;
}
bool check(vii w){
for(int i=1;i<n;i++){
bool ok = 0;
if(cnt(w[i]) == cnt(w[i-1])) ok = 1;
if(cnt1(w[i]) == cnt1(w[i-1])) ok = 1;
if(!ok) return 0;
}
return 1;
}
ll rec(vii way, vii used){
if(sz(way) == n) return (int)check(way);
ll ans = 0;
for(int i=0;i<n;i++){
if(!used[i]){
used[i] = 1;
way.pb(a[i]);
ans += rec(way, used);
used[i] = 0;
way.pop_back();
}
}
return ans;
}
void solve(){
fastios
cin>>n;
vii used(n, 0);
for(int i=0;i<n;i++) cin>>a[i];
cout<<rec({}, used)<<"\n";
return;
}
int main(){
fastios
int t = 1;
if(t) solve();
else {
cin>>t;
while (t--) solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1324 ms |
388 KB |
Output is correct |
| 7 |
Correct |
1256 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1817 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1263 ms |
492 KB |
Output is correct |
| 10 |
Execution timed out |
3077 ms |
364 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
