답안 #673805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673805 2022-12-22T05:32:39 Z smartmonky 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
7 ms 3444 KB
#include <bits/stdc++.h>
 
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
 
using namespace std;
 
void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
const int N =  (1 << 21) + 2;
int dp[N][25], a[25], bit[25], ter[25], used[N];
int ful;
int getbits(int x){
	int res = 0;
	while(x > 0){
		res += x % 2;
		x /= 2;
	}
	return res;
}
int getter(int x){
	int res = 0;
	while(x > 0){
		res += (x % 3 == 1);
		x /= 3;
	}
	return res;
}
 
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		ful += (1 << i);
		cin >> a[i];
		bit[i] = getbits(a[i]);
		used[getbits(a[i])] = 1;
		ter[i] = getter(a[i]);
		dp[(1 << i)][i] = 1;
	}
	for(int i = 1; i < (1 << (n + 1)); i++){
		for(int j = 1; j <= n; j++){
			if(dp[i][j] == 0 ||  (i  & (1 << j)) == 0)continue;
				for(int k = 1; k  <= n; k++){
					if((i & (1 << k)))continue;
					if(bit[k] == bit[j] || ter[k] == ter[j])
						dp[i + (1 << k)][k] += dp[i][j];
				}
		}
	}
	int ans = 0;
	for(int i = 1;  i <= n; i++){
		ans += dp[ful][i];
	}
	cout << ans;
}

Compilation message

beauty.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main(){
      | ^~~~
beauty.cpp: In function 'void fp(std::string)':
beauty.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 248 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 528 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Incorrect 7 ms 3444 KB Output isn't correct
12 Halted 0 ms 0 KB -