oj.uz

Submission #41132

# Submission time Handle Problem Language Result Execution time Memory
41132 2018-02-13T04:52:09 Z wzy Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 173088 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);
			}
		}
	}
	memset(dp, - 1 , sizeof dp);
	int ans = 0;
	for(int i = 0 ; i < n ; i++){
		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

# Verdict Execution time Memory Grader output
1 Correct 125 ms 172664 KB Output is correct
2 Correct 120 ms 172704 KB Output is correct
3 Correct 119 ms 172968 KB Output is correct
4 Correct 126 ms 172968 KB Output is correct
5 Correct 126 ms 172968 KB Output is correct
6 Correct 123 ms 172968 KB Output is correct
7 Correct 119 ms 172968 KB Output is correct
8 Correct 123 ms 172968 KB Output is correct
9 Correct 125 ms 172968 KB Output is correct
10 Correct 125 ms 172968 KB Output is correct
11 Correct 133 ms 172968 KB Output is correct
12 Correct 130 ms 172968 KB Output is correct
13 Correct 181 ms 172968 KB Output is correct
14 Correct 505 ms 173036 KB Output is correct
15 Correct 690 ms 173036 KB Output is correct
16 Correct 425 ms 173088 KB Output is correct
17 Correct 595 ms 173088 KB Output is correct
18 Correct 359 ms 173088 KB Output is correct
19 Execution timed out 3031 ms 173088 KB Time limit exceeded
20 Halted 0 ms 0 KB -