답안 #90117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90117 2018-12-20T11:17:11 Z Hideo 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
2243 ms 263168 KB
#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(){
      ^
# 결과 실행 시간 메모리 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 -