oj.uz

답안 #673819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673819 2022-12-22T05:49:51 Z smartmonky 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 258 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()
 
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) + 1;
long long dp[N][22];
int a[22], bit[22], ter[22];
long long ful;

int getbits(int x){
	int res = 0;
	while(x > 0){
		res += x % 2;
		x >>= 1;
	}
	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)) || i + (1 << k) > ful)continue;
					if(bit[k] == bit[j] || ter[k] == ter[j])
						dp[i + (1 << k)][k] += dp[i][j];
				}
		}
	}
	long long ans = 0;
	for(int i = 1;  i <= n; i++){
		ans += dp[ful][i];
	}
	cout << ans;
}

Compilation message

beauty.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 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 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 8 ms 5700 KB Output is correct
12 Correct 6 ms 5844 KB Output is correct
13 Correct 38 ms 22848 KB Output is correct
14 Correct 178 ms 90612 KB Output is correct
15 Correct 170 ms 90592 KB Output is correct
16 Correct 190 ms 90592 KB Output is correct
17 Correct 194 ms 90508 KB Output is correct
18 Correct 163 ms 90592 KB Output is correct
19 Runtime error 258 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -