oj.uz

답안 #673983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673983 2022-12-22T13:34:34 Z Cutebol 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 2347 ms 205512 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
   
const int N = 25 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e9 ;

int n ;
int a[N] , b[N] , dp[(1<<20)+5][25] ;

int func(int x){
	int res = 0 ;
	while ( x ){
		res += ( x % 3 == 1 ) ;
		x /= 3 ;
	} 
	return res ;
}

int rec ( int mask , int last ){
	
	if ( __builtin_popcount(mask) == n ) return 1 ;
	if ( last != -1 && dp[mask][last] != -1 ) return dp[mask][last] ;
	int ans = 0 ;
	for ( int i = 0 ; i < n ; i ++ ){
		if ( mask&(1<<i) ) continue ;
		if ( last == -1 || a[i] == a[last] || b[i] == b[last] ) ans += rec( mask|(1<<i) , i ) ;
	}
	return dp[mask][last] = ans ;
	
}

void solve(){
	
	cin >> n ;
	for ( int i = 0 ; i < n ; i ++ ){
		int x ;
		cin >> x ;
		a[i] = __builtin_popcount(x) ;
		b[i] = func(x) ;
	}
	
	memset( dp , -1 , sizeof(dp) ) ;
	cout << rec( 0 , -1 ) ;
}
 
signed main(){
//  fopn("blocks") ;
    Scaramouche ;
    int t = 1 ;
//    	cin >> t ;
    while ( t -- ) solve() ; 
}

Compilation message

beauty.cpp: In function 'void fopn(std::string)':
beauty.cpp:5:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:5:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 205416 KB Output is correct
2 Correct 73 ms 205392 KB Output is correct
3 Correct 76 ms 205396 KB Output is correct
4 Correct 75 ms 205460 KB Output is correct
5 Correct 78 ms 205500 KB Output is correct
6 Correct 75 ms 205396 KB Output is correct
7 Correct 87 ms 205392 KB Output is correct
8 Correct 90 ms 205420 KB Output is correct
9 Correct 86 ms 205440 KB Output is correct
10 Correct 75 ms 205448 KB Output is correct
11 Correct 87 ms 205440 KB Output is correct
12 Correct 86 ms 205448 KB Output is correct
13 Correct 132 ms 205440 KB Output is correct
14 Correct 406 ms 205428 KB Output is correct
15 Correct 430 ms 205508 KB Output is correct
16 Correct 365 ms 205500 KB Output is correct
17 Correct 415 ms 205460 KB Output is correct
18 Correct 292 ms 205388 KB Output is correct
19 Correct 2205 ms 205504 KB Output is correct
20 Correct 2347 ms 205512 KB Output is correct