oj.uz

답안 #41131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41131 2018-02-13T04:51:10 Z wzy 아름다운 순열 (IZhO12_beauty) C++11
0 / 100
 3000 ms 173072 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define pb push_back
#define S second
#define pii pair<int,int>
#define int long long
int n;
vector<int> v;
vector<int> adj[30];
int dp[21][1LL<<20];
pair<int,int> f(int x){
	int a1 = 0 , a2 = 0;
	int z =x;
	while(z > 0){
		if(z%2 == 1) a1++;
		z/= 2;
	}
	z = x;
	while(z > 0){
		if(z%3 == 1) a2++;
		z/=3;
	}
	return pair<int,int>(a1, a2);
}


int solve(int i , int mask){
	if(dp[i][mask] != -1) return dp[i][mask];
	int maxxi = 1<<n;
	maxxi--;
	if(mask == maxxi) return 1;
	dp[i][mask] = 0;
	for(int j = 0 ; j < adj[i].size() ; j++){
		int v = adj[i][j];
		if(mask & 1<<v) continue;
		dp[i][mask] += solve(v , 1<<v | mask);
	}
	return dp[i][mask];
}

int32_t main(){
	cin>>n;
	v.resize(n);
	for(int i = 0 ; i < n ;i++) cin>>v[i];
	for(int i = 0 ; i <n; i++){
		for(int j = i + 1 ; j < n;j++){
			if(f(v[i]).F == f(v[j]).F || f(v[i]).S ==f(v[j]).S){
				adj[i].pb(j);
				adj[j].pb(i);
			}
		}
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i++){
		memset(dp , -1 , sizeof dp);
		ans+= solve(i , 1<<i);
	}
	cout<<ans<<endl;
}

Compilation message

beauty.cpp: In function 'long long int solve(long long int, long long int)':
beauty.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < adj[i].size() ; j++){
                    ^

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 172792 KB Output is correct
2 Correct 197 ms 172792 KB Output is correct
3 Correct 234 ms 172836 KB Output is correct
4 Correct 238 ms 172868 KB Output is correct
5 Correct 235 ms 172868 KB Output is correct
6 Correct 463 ms 172928 KB Output is correct
7 Correct 459 ms 172944 KB Output is correct
8 Correct 463 ms 173072 KB Output is correct
9 Correct 470 ms 173072 KB Output is correct
10 Correct 465 ms 173072 KB Output is correct
11 Correct 680 ms 173072 KB Output is correct
12 Correct 653 ms 173072 KB Output is correct
13 Correct 1098 ms 173072 KB Output is correct
14 Execution timed out 3025 ms 173072 KB Time limit exceeded
15 Halted 0 ms 0 KB -