-
Notifications
You must be signed in to change notification settings - Fork 23
/
square.cpp
71 lines (57 loc) · 1.25 KB
/
square.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
#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <functional>
using namespace std;
unordered_map<int, bool> squares;
void square(int N, vector<int>& a) {
vector<int> seq;
vector<bool> visited(N);
vector< vector<int> > adj(N);
sort(a.begin(), a.end());
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
if (squares.count(a[i] + a[j])) {
adj[i].push_back(j);
adj[j].push_back(i);
}
function<bool(int)> sequence = [&](int s) {
visited[s] = true;
seq.push_back(a[s]);
if (seq.size() == N)
return true;
for (int& u: adj[s])
if (!visited[u] && sequence(u))
return true;
seq.pop_back();
visited[s] = false;
return false;
};
for (int i = 0; i < N && !sequence(i); i++) {
seq.clear();
fill(visited.begin(), visited.end(), false);
}
if (seq.empty())
cout << "No solution";
else
for (int i = 0; i < N; i++)
cout << seq[i] << " ";
cout << endl;
}
int main() {
freopen("square.in", "r", stdin);
freopen("output.out", "w", stdout);
// preprocess
for (int i = 1; i < 10; i++)
squares[i * i] = true;
int N;
while (cin >> N && N) {
vector<int> a(N);
for (int i = 0; i < N; i++)
cin >> a[i];
square(N, a);
}
return 0;
}