oj.uz

Submission #1111843

# Submission time Handle Problem Language Result Execution time Memory
1111843 2024-11-13T04:30:33 Z Tsagana Beautiful row (IZhO12_beauty) C++14
100 / 100
 1250 ms 205640 KB 
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int l[25];
int s[25][5];
int dp[2000000][25];

int to2(int x) {
	int ans = 0;
	while (x) {if (x%2 == 1) ans++; x /= 2;}
	return ans;
}
int to3(int x) {
	int ans = 0;
	while (x) {if (x%3 == 1) ans++; x /= 3;}
	return ans;
}

void solve () {
	l[0] = 1; for (int i = 1; i <= 20; i++) l[i] = l[i-1]*2;

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		s[i][2] = to2(x);
		s[i][3] = to3(x);
	}
	for (int i = 0; i < n; i++) dp[l[i]][i] = 1;
	
	for (int i = 0; i < l[n]; i++)
		for (int j = 0; j < n; j++)
		for (int k = 0; k < n; k++) {
			if (i & l[k]) continue ;
			if (s[j][2] == s[k][2] || s[j][3] == s[k][3]) {
				dp[i|l[k]][k] += dp[i][j];
			}
		}
	
	int ans = 0;
	for (int i = 0; i < n; i++) ans += dp[l[n]-1][i];
	cout << ans;
}
signed main() {IOS solve(); return 0;}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 10 ms 4688 KB Output is correct
12 Correct 9 ms 4760 KB Output is correct
13 Correct 36 ms 14940 KB Output is correct
14 Correct 226 ms 51784 KB Output is correct
15 Correct 140 ms 51892 KB Output is correct
16 Correct 256 ms 51892 KB Output is correct
17 Correct 274 ms 51784 KB Output is correct
18 Correct 269 ms 51784 KB Output is correct
19 Correct 1250 ms 205640 KB Output is correct
20 Correct 686 ms 205548 KB Output is correct