Submission #1020074

#TimeUsernameProblemLanguageResultExecution timeMemory
1020074MinbaevBeautiful row (IZhO12_beauty)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second #define int long long #define pii pair<int,int> template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; void solve(){ cin >> n; vector<int>a(n); for(auto &to:a)cin >> to; vector<int>b(n); for(int i = 0;i<n;i++){ int cnt = 0; for(int j = 1;j>=0;j--){ if((a[i] / binpow(3,j)) % 3 == 1)cnt += 1; } b[i] = cnt; } for(auto &to:a){ int cnt = 0; for(int i = 32;i>=0;i--){ if(to >> i & 1)cnt += 1; } to = cnt; } //~ for(auto to:a)cout << to << " "; //~ cout << "\n"; //~ for(auto to:b)cout << to << " "; //~ cout << "\n\n"; int dp[(1<<n)][n]{}; for(int i = 0;i<n;i++){ dp[(1<<i)][i] = 1; } for(int mask = 1;mask<(1<<n);mask++){ for(int i = 0;i<n;i++){ if(!(mask >> i & 1))continue; for(int j = 0;j<n;j++){ if(mask >> j & 1)continue; if(a[i] != a[j] && b[i] != b[j])continue; dp[(mask|(1<<j))][j] += dp[mask][i]; } } } int ans = 0; for(int i = 0;i<n;i++){ ans += dp[(1<<n)-1][i]; } cout << ans << "\n"; //~ for(int mask = 1;mask<(1<<n);mask++){ //~ for(int i = 0;i<n;i++){ //~ cout << (mask >> i & 1); //~ } //~ cout << "\n"; //~ for(int i = 0;i<n;i++){ //~ cout << dp[mask][i] << " "; //~ } //~ cout << "\n"; //~ } } signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...