oj.uz

답안 #716443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716443 2023-03-30T06:10:14 Z vjudge1 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 836 ms 146436 KB 
 #include <bits/stdc++.h>
#define f first
#define s second 
#define ent '\n'
#define int long long

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

//typedef long double ld;
typedef long long ll;
using namespace std;
 
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}

struct seg{
	int mx1=0,mx2=0,ans=0;
};

const string out[2]={"NO\n","YES\n"};
const ll dx[]={0,0,1,-1,-1,1,1,-1};  
const ll dy[]={1,-1,0,0,-1,1,-1,1};
const int md=998244353;
const int mod=1e9+7;
const int mx=8e5+12; 
const int tst=1e5;
const bool T=0;

vector<int> g[mx];
int dp[22][1<<21];
int q[mx];
int a[mx];
int n,m,k;

void Press_Fn_with_F11(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>q[i];
	sort(q+1,q+n+1);
	for(int i=1;i<=n;i++){
		int a=0,b=0,x=q[i];
		while(x){
			a+=x%2;
			x/=2;
		}
		x=q[i];
		while(x){
			b+=(x%3==1);
			x/=3;
		}
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			int c=0,d=0,x=q[j];
			while(x){
				c+=x%2;
				x/=2;
			}
			x=q[j];
			while(x){
				d+=(x%3==1);
				x/=3;
			}
			if(a==c || b==d)g[i].push_back(j);
		}
		dp[i][(1ll<<(i-1))]=1;
	}
	for(int i=1;i<(1ll<<n);i++){
		for(int j=1;j<=n;j++){
			if(!(i&(1ll<<(j-1))))continue;
			for(int x:g[j]){
				if((i&(1ll<<(x-1))))continue;
				dp[x][i+(1ll<<(x-1))]+=dp[j][i];
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans+=dp[i][(1ll<<n)-1];
	cout<<ans<<ent;
}

signed main(){	
    ios_base::sync_with_stdio(0);
    cin.tie(0);		
    cout.tie(0);
    int Ersayin_abi_crush=1;
    if(T)cin>>Ersayin_abi_crush;
    for(int i=1;i<=Ersayin_abi_crush;i++){
//    	cout<<"Case "<<i<<": ";
    	Press_Fn_with_F11();
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 10 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 10 ms 19192 KB Output is correct
8 Correct 11 ms 19184 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 10 ms 19156 KB Output is correct
11 Correct 16 ms 20692 KB Output is correct
12 Correct 16 ms 20700 KB Output is correct
13 Correct 46 ms 26080 KB Output is correct
14 Correct 174 ms 48884 KB Output is correct
15 Correct 184 ms 48952 KB Output is correct
16 Correct 181 ms 48888 KB Output is correct
17 Correct 164 ms 48892 KB Output is correct
18 Correct 128 ms 48952 KB Output is correct
19 Correct 836 ms 146420 KB Output is correct
20 Correct 817 ms 146436 KB Output is correct