oj.uz

Submission #17310

# Submission time Handle Problem Language Result Execution time Memory
17310 2015-11-20T00:28:19 Z gs14004 Beautiful row (IZhO12_beauty) C++14
100 / 100
 984 ms 165560 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

bool adj[20][20];
int a[20], n;

lint dp[1<<20][20];

lint f(int bit, int pos){
	if(bit == (1<<n) - 1) return 1;
	if(~dp[bit][pos]) return dp[bit][pos];
	lint ret = 0;
	for(int i=0; i<n; i++){
		if(((bit >> i) & 1) == 0 && adj[pos][i]){
			ret += f(bit | 1 << i, i);
		}
	}
	return ret;
}

bool mat(int p, int q){
	int cp = 0, cq = 0;
	for(int i=0; i<31; i++){
		if((p >> i) & 1) cp++;
		if((q >> i) & 1) cq++;
	}
	if(cp == cq) return 1;
	cp = cq = 0;
	while(p || q){
		if(p%3 == 1) cp++;
		if(q%3 == 1) cq++;
		p /= 3, q /= 3;
	}
	return cp == cq;
}

inline int get(int b, int x){
	return (b >> x) & 1;
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(mat(a[i], a[j])) adj[i][j] = adj[j][i] = 1;
		}
	}
	lint ret = 0;
	for(int i=0; i<n; i++){
		dp[(1<<n) - 1][i] = 1;
	}
	for(int i=(1<<n)-2; i>=0; i--){
		for(int j=0; j<n; j++){
			if(get(i, j) == 0) continue;
			for(int k=0; k<n; k++){
				if(get(i, k) == 0 && adj[j][k]){
					dp[i][j] += dp[i |(1<<k)][k];
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		ret += dp[1<<i][i];
	}
	printf("%lld",ret);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 165560 KB Output is correct
2 Correct 0 ms 165560 KB Output is correct
3 Correct 0 ms 165560 KB Output is correct
4 Correct 0 ms 165560 KB Output is correct
5 Correct 0 ms 165560 KB Output is correct
6 Correct 0 ms 165560 KB Output is correct
7 Correct 0 ms 165560 KB Output is correct
8 Correct 0 ms 165560 KB Output is correct
9 Correct 0 ms 165560 KB Output is correct
10 Correct 0 ms 165560 KB Output is correct
11 Correct 9 ms 165560 KB Output is correct
12 Correct 9 ms 165560 KB Output is correct
13 Correct 41 ms 165560 KB Output is correct
14 Correct 201 ms 165560 KB Output is correct
15 Correct 192 ms 165560 KB Output is correct
16 Correct 199 ms 165560 KB Output is correct
17 Correct 210 ms 165560 KB Output is correct
18 Correct 200 ms 165560 KB Output is correct
19 Correct 984 ms 165560 KB Output is correct
20 Correct 905 ms 165560 KB Output is correct