답안 #673807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673807 2022-12-22T05:33:57 Z smartmonky 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
218 ms 262144 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];
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]);
		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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 10 ms 6356 KB Output is correct
12 Correct 8 ms 6612 KB Output is correct
13 Correct 42 ms 25956 KB Output is correct
14 Correct 175 ms 102908 KB Output is correct
15 Correct 160 ms 102860 KB Output is correct
16 Correct 169 ms 102844 KB Output is correct
17 Correct 190 ms 102904 KB Output is correct
18 Correct 154 ms 102908 KB Output is correct
19 Runtime error 218 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -