oj.uz

Submission #382264

# Submission time Handle Problem Language Result Execution time Memory
382264 2021-03-26T21:01:30 Z knightron0 Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 172908 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double
 
const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 25;
 
int n;
int a[MAXN], b[MAXN], t[MAXN], dp[MAXN][(1<<21)];
 
int check(int i, int j){
	if(b[i] == b[j] || t[i] == t[j]) return true;
	return false;
}
 
int f(int i, int mask){
	if(mask == (1<<i)){
		return 1;
	}
	if(dp[i][mask] != -1){
		return dp[i][mask];
	}
	int res = 0;
	for(int j= 0;j<n;j++){
		if(!(mask & (1<<j)) || (j == i)) continue;
		if(check(i, j)){
			res += f(j, mask ^ (1<<i));
		}
	}
	return dp[i][mask] = res;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    cin>>n;
    for(int i= 0;i<=n;i++){
    	for(int j= 0;j<=(1<<n);j++){
    		dp[i][j] = -1;
    	}
    }
    for(int i= 0;i<n;i++){
    	b[i] = 0;
    	t[i] = 0;
    	cin>>a[i];
    	int x = a[i];
    	while(x){
			t[i] += ((x%3)==1);
			x /= 3;
		}
		x = a[i];
		while(x){
			b[i] += ((x%2)==1);
			x /= 2;
		}
    }
    int ans = 0;
    for(int i= 0;i<n;i++){
    	ans += f(i, (1<<n)-1);
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 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 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 14 ms 2412 KB Output is correct
12 Correct 10 ms 2412 KB Output is correct
13 Correct 74 ms 9196 KB Output is correct
14 Correct 568 ms 39532 KB Output is correct
15 Correct 832 ms 39528 KB Output is correct
16 Correct 448 ms 39532 KB Output is correct
17 Correct 706 ms 39532 KB Output is correct
18 Correct 346 ms 39532 KB Output is correct
19 Execution timed out 3101 ms 172908 KB Time limit exceeded
20 Halted 0 ms 0 KB -