oj.uz

답안 #673793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673793 2022-12-22T03:50:55 Z Baytoro 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 2443 ms 172680 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e18,mod=998244353;
int n,m,k;
const int N=25;
#define cnt __builtin_popcount
int a[N],b[N];
int g2(int x){
	int res=0;
	while(x){
		res+=(x%2);
		x/=2;
	}
	return res;
}
int g3(int x){
	int res=0;
	while(x){
		res+=(x%3==1);
		x/=3;
	}
	return res;
}
int dp[(1<<20)+5][21];
int calc(int mask, int last){
	if(cnt(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) ans+=calc(mask|(1<<i),i);
		else if(a[i]==a[last] || b[i]==b[last]) ans+=calc(mask|(1<<i),i);
	}
	return dp[mask][last]=ans;
}
void solve(){
	memset(dp,-1,sizeof(dp));
	cin>>n;
	for(int i=0;i<n;i++){
		int x;cin>>x;
		a[i]=g2(x);
		b[i]=g3(x);
	}
	cout<<calc(0,-1);
}
main(){
	//fopn("newbarn");
	//ios;
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}
/*
3
2 1 1000000000
1 1 1000000000
1 1 1000000000
*/

Compilation message

beauty.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main(){
      | ^~~~
beauty.cpp: In function 'void fopn(std::string)':
beauty.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 172620 KB Output is correct
2 Correct 62 ms 172540 KB Output is correct
3 Correct 69 ms 172600 KB Output is correct
4 Correct 69 ms 172564 KB Output is correct
5 Correct 70 ms 172648 KB Output is correct
6 Correct 63 ms 172580 KB Output is correct
7 Correct 63 ms 172584 KB Output is correct
8 Correct 64 ms 172612 KB Output is correct
9 Correct 64 ms 172600 KB Output is correct
10 Correct 67 ms 172628 KB Output is correct
11 Correct 76 ms 172644 KB Output is correct
12 Correct 75 ms 172628 KB Output is correct
13 Correct 126 ms 172612 KB Output is correct
14 Correct 417 ms 172660 KB Output is correct
15 Correct 414 ms 172620 KB Output is correct
16 Correct 330 ms 172680 KB Output is correct
17 Correct 413 ms 172620 KB Output is correct
18 Correct 272 ms 172652 KB Output is correct
19 Correct 2215 ms 172648 KB Output is correct
20 Correct 2443 ms 172648 KB Output is correct