oj.uz

답안 #336127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336127 2020-12-14T19:07:50 Z tevdore 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 3000 ms 45648 KB 
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int const N = 1 << 23;
int n;
ll a[25], dp[N][25];
ll ans;
bool check1(int x, int y) {
	int r1 = 0, r2 = 0;
	while(x) {
		r1 += x % 2;
		x /= 2;
	}
	while(y) {
		r2 += y % 2;
		y /= 2;
	}
	if(r1 == r2) return true;
	return false;
}
bool check2(int x, int y) {
	int r1 = 0, r2 = 0;
	while(x) {
		r1 += (x % 3 == 1);
		x /= 3;
	}
	while(y) {
		r2 += (y % 3 == 1);
		y /= 3;
	}
	if(r1 == r2) return true;
	return false;
	
}
main() {
	ios::sync_with_stdio(0);
	cin.tie();
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int mask = 1 << n;
	mask--;
	for(int i = 1; i <= mask; i++) {
		for(int j = 0; j < n; j++) {
			if(i >> j & 1) {
				int x = i ^ (1 << j);
				if(!x) {
					dp[i][j + 1] = 1;
					continue;
				}
				for(int z = 0; z < n; z++) {
					if((x >> z) & 1) {
						bool f1 = false, f2 = false;
						f1 = check1(a[j + 1], a[z + 1]);
						f2 = check2(a[j + 1], a[z + 1]);
						if(f1 || f2) dp[i][j + 1] += dp[x][z + 1];
					}
				}
			}
		}
	}
	for(int j = 0; j < n; j++) ans += dp[mask][j + 1];
	cout << ans << "\n";
}

Compilation message

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

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 5 ms 492 KB Output is correct
11 Correct 145 ms 3632 KB Output is correct
12 Correct 140 ms 3564 KB Output is correct
13 Correct 719 ms 13292 KB Output is correct
14 Execution timed out 3078 ms 45648 KB Time limit exceeded
15 Halted 0 ms 0 KB -