-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
996.cpp
110 lines (106 loc) · 3.2 KB
/
996.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
void print(const vector<int>& vec) {
for (int a : vec) cout << a << ' ';
cout << '\n';
}
int N;
int count;
unordered_map<int, int> B;
unordered_map<int, vector<int> > squares;
vector<int> vec;
void test() {
//print(vec);
if (vec.size() == N) { count++; return; }
for (int cand : squares[vec.back()]) {
if (B[cand] == 0) continue;
B[cand]--;
vec.push_back(cand);
test();
vec.pop_back();
B[cand]++;
}
}
bool is_square(const int a) {
const int r = (int)sqrt(a);
return a == r * r;
}
public:
int numSquarefulPerms(vector<int>& A) {
N = A.size();
count = 0;
for (const int& a : A) B[a]++;
for (auto it : B) {
for (auto it_ : B) {
if (it.first <= it_.first) continue;
if (is_square(it.first + it_.first)) {
//cout << "find pair " << it.first << " and " << it_.first << '\n';
squares[it.first].push_back(it_.first);
squares[it_.first].push_back(it.first);
}
}
if (is_square(it.first * 2)) {
//cout << "find pair " << it.first << " and " << it.first << '\n';
squares[it.first].push_back(it.first);
}
}
for (auto it : B) {
B[it.first]--;
vec.push_back(it.first);
test();
vec.pop_back();
B[it.first]++;
}
return count;
}
};
__________________________________________________________________________________________________
sample 8528 kb submission
class Solution {
public:
int numSquarefulPerms(vector<int> &A) {
preProcess(A);
dfs(A, 0, 0);
return result;
}
void dfs(vector<int> &A, int depth, int curr) {
if (depth == A.size()) {
result++; return;
}
int same = -1;
for (int i = 0; i < A.size(); i++) {
if (depth > 0 && !isSquare[curr][i]) {
continue;
}
if (A[i] != same && !isVisited[i]) {
isVisited[i] = 1;
dfs(A, depth + 1, i);
isVisited[i] = 0;
same = A[i];
}
}
}
private:
static const int MAXN = 14;
int isSquare[MAXN][MAXN];
int isVisited[MAXN];
int result;
void preProcess(vector<int> &A) {
sort(A.begin(), A.end());
memset(isSquare, 0x00, MAXN * MAXN * sizeof(int));
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < i; j++) {
int y = A[i] + A[j];
int x = int(sqrt(double(y)));
if (x * x == y) {
isSquare[i][j] = 1;
isSquare[j][i] = 1;
}
}
}
memset(isVisited, 0x00, MAXN * sizeof(int));
result = 0;
}
};
__________________________________________________________________________________________________