답안 #90112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90112 2018-12-20T10:55:49 Z YottaByte 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
2 ms 376 KB
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, ans;
vector < int > a;
set < vector < int > > st;

inline bool count(int a, int b)
{
	int resa, resb;
	resa = resb = 0;
	
	while(a)
	{
		resa += (a % 3 == 1);
		a /= 3;
	}
	
	while(b)
	{
		resb += (b % 3 == 1);
		b /= 3;
	}
	return (resa == resb);
}

inline bool check(vector < int > b)
{
	int c = 0;
	for(int i = 0; i < n - 1; i++)
	{
		if(__builtin_popcount(b[i]) != __builtin_popcount(b[i + 1]) && !count(b[i], b[i + 1])) return false;
	}
	return true;
}

int fact(int n)
{
	int res = 1;
	for(int i = 2; i <= n; i++)
	{
		res *= i;
	}
	return res;
}

void out(vector < int > tmp)
{
	for(int i = 0; i < tmp.size(); i++)
		cout << tmp[i] << " ";
	puts("");
}

void bt( vector < int > b, vector < int > u )
{
	if(b.size() == n)
	{
		//out(b);
		ans += check(b);
		return;
	}
	
	for(int i = 0; i < n; i++)
	{
		if(!u[i])
		{
			u[i] = 1;
			b.push_back(a[i]);
			bt( b, u );
			b.pop_back();
			u[i] = 0;
		}
	}
}

main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int x; cin >> x;
		a.push_back(x);
	}
	
	sort(a.begin() + 1, a.begin() + 1 + n);
	
	int mx = fact(n);
	vector < int > t, t1;
	for(int i = 0; i < n; i++) t.push_back(0);
	t1.clear();
	bt( t1, t );
	
	cout << ans << endl;
}

Compilation message

beauty.cpp: In function 'bool check(std::vector<int>)':
beauty.cpp:30:6: warning: unused variable 'c' [-Wunused-variable]
  int c = 0;
      ^
beauty.cpp: In function 'void out(std::vector<int>)':
beauty.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tmp.size(); i++)
                 ~~^~~~~~~~~~~~
beauty.cpp: In function 'void bt(std::vector<int>, std::vector<int>)':
beauty.cpp:57:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(b.size() == n)
     ~~~~~~~~~^~~~
beauty.cpp: At global scope:
beauty.cpp:77:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:88:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = fact(n);
      ^~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -