#include <bits/stdc++.h>
using namespace std;
const int N = 27;
const int INF = 1e9 + 7;
vector < int > g[N];
set < string > ans;
map < int, char > mp;
int a[N], b[N], t[N], h[N];
int us[N], nd[N];
int n;
int make_bin (int x, int c){
if (x == 0)
return c;
if (x % 2 == 1)
c++;
return make_bin (x / 2, c);
}
int make_ter (int x, int c){
if (x == 0)
return c;
if (x % 3 == 1)
c++;
return make_ter(x / 3, c);
}
void dfs (int v, int c, string s){
us[v]++;
if (c == n){
nd[v]++;
ans.insert(s);
return;
}
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i];
if (us[to] != nd[to])
dfs(to, c + 1, s + mp[a[to]]);
}
nd[v]++;
}
main(){
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
h[i] = a[i];
b[i] = make_bin(a[i], 0);
t[i] = make_ter(a[i], 0);
}
sort (h, h + n);
for (int i = 0; i < n; i++)
if (!i || h[i] != h[i - 1])
mp[h[i]] = i + 'a';
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (b[i] == b[j] || t[i] == t[j]){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
for (int i = 0; i < n; i++){
fill (nd, nd + N, 1);
fill (us, us + N, 0);
string tmp; tmp += mp[a[i]];
dfs(i, 1, tmp);
}
cout << ans.size();
}
Compilation message
beauty.cpp: In function 'void dfs(int, int, std::__cxx11::string)':
beauty.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
beauty.cpp: At global scope:
beauty.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Correct |
2 ms |
440 KB |
Output is correct |
| 5 |
Correct |
2 ms |
440 KB |
Output is correct |
| 6 |
Correct |
7 ms |
872 KB |
Output is correct |
| 7 |
Correct |
2 ms |
872 KB |
Output is correct |
| 8 |
Runtime error |
2243 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Halted |
0 ms |
0 KB |
- |
