답안 #339835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339835	2020-12-26T09:34:48 Z	nandonathaniel	아름다운 순열 (IZhO12_beauty)	C++14	0 / 100	3000 ms	164664 KB

beauty

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
int n;
long long dp[1<<MAXN][MAXN];
int a[MAXN];

int binary(int x){
	return __builtin_popcount(x);
}

int ternary(int x){
	int ret=0;
	while(x>0){
		if(x%3==1)ret++;
		x/=3;
	}
	return ret;
}

long long DP(int mask,int last){
	if(mask==((1<<n)-1))return 1;
	long long &ret=dp[mask][last];
	if(ret!=-1)return ret;
	ret=0;
	for(int i=0;i<n;i++){
		if(!(mask & (1<<i))){
			if(binary(a[last])==binary(a[i]) || ternary(a[last])==ternary(a[i]))ret+=DP(mask+(1<<i),i);
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];
	memset(dp,-1,sizeof(dp));
	long long ans=0;
	for(int i=0;i<n;i++)ans+=DP(1<<i,i);
	cout << ans << '\n';
	return 0;
}

Compilation message

beauty.cpp:5: warning: ignoring #pragma GCC option [-Wunknown-pragmas]
    5 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      |

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	164460 KB	Output is correct
2	Correct	80 ms	164460 KB	Output is correct
3	Correct	92 ms	164460 KB	Output is correct
4	Correct	82 ms	164460 KB	Output is correct
5	Correct	81 ms	164460 KB	Output is correct
6	Correct	80 ms	164460 KB	Output is correct
7	Correct	80 ms	164588 KB	Output is correct
8	Correct	85 ms	164460 KB	Output is correct
9	Correct	82 ms	164460 KB	Output is correct
10	Correct	91 ms	164460 KB	Output is correct
11	Correct	96 ms	164460 KB	Output is correct
12	Correct	94 ms	164460 KB	Output is correct
13	Correct	187 ms	164588 KB	Output is correct
14	Correct	793 ms	164588 KB	Output is correct
15	Correct	624 ms	164460 KB	Output is correct
16	Correct	886 ms	164664 KB	Output is correct
17	Correct	912 ms	164548 KB	Output is correct
18	Correct	707 ms	164460 KB	Output is correct
19	Execution timed out	3063 ms	164460 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-