# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527664 | 2022-02-18T00:25:28 Z | theshadow_04 | Beautiful row (IZhO12_beauty) | C++14 | 8 ms | 1868 KB |
// annotshy #include <bits/stdc++.h> #define Task "beauty" #define F first #define S second using namespace std; const int maxn = 100005; int n, a[maxn]; int dp[(1 << 20) + 5][25], match[25][25]; int binary_1(int x) { int res = 0; while(x) { res += (x % 2 == 1); x /= 2; } return res; } int ternary_1(int x) { int res = 0; while(x) { res += (x % 3 == 1); x /= 3; } return res; } bool ok(int x, int y) { if(binary_1(x) == binary_1(y)) return 1; if(ternary_1(x) == ternary_1(y)) return 1; return 0; } void Solve(int Test) { cin >> n; for(int i = 1; i <= n; ++ i) cin >> a[i]; for(int i = 1; i <= n; ++ i) { for(int j = i + 1; j <= n; ++ j) { match[i][j] = match[j][i] = ok(a[i], a[j]); } dp[(1 << (i - 1))][i] = 1; } for(int mask = 0; mask < (1 << n); ++ mask) { for(int i = 1; i <= n; ++ i) { if(!(mask >> (i - 1) & 1)) continue; for(int j = 1; j <= n; ++ j) { if(!match[i][j]) continue; if(!(mask >> (j - 1) & 1)) continue; dp[mask][i] += dp[mask ^ (1 << (i - 1))][j]; } } } int res = 0; for(int i = 1; i <= n; ++ i) res += dp[(1 << n) - 1][i]; cout << res << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); if(fopen(Task".in", "r")) { freopen(Task".in", "r", stdin); freopen(Task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++ i) { Solve(i); } } /*no pain no gain*/
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 316 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Incorrect | 8 ms | 1868 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |