oj.uz

Submission #41135

# Submission time Handle Problem Language Result Execution time Memory
41135 2018-02-13T05:00:30 Z wzy Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 145236 KB 
#include <stdio.h>
#include <vector>
using namespace std;
#define F first
#define pb push_back
#define S second
#define pii pair<int,int>
int n;
vector<int> v;
vector<int> adj[30];
long long dp[21][1<<20];
bool vis[21][1<<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);
}


long long solve(int i , int mask){
	if(vis[i][mask]) return dp[i][mask];
	vis[i][mask] = true;
	int maxxi = 1<<n;
	maxxi--;
	if(mask == maxxi) return dp[i][mask] = 1;
	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];
}

int main(){
	scanf("%d" , &n);
	v.resize(n);
	for(int i = 0 ; i < n ;i++) scanf("%d" , &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);
			}
		}
	}
	long long ans = 0;
	for(int i = 0 ; i < n ; i++){
		ans+= solve(i , 1<<i);
	}
	printf("%lld\n" , ans);
}

Compilation message

beauty.cpp: In function 'long long int solve(int, int)':
beauty.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < adj[i].size() ; j++){
                    ^
beauty.cpp: In function 'int main()':
beauty.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
                  ^
beauty.cpp:46:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0 ; i < n ;i++) scanf("%d" , &v[i]);
                                                 ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 2 ms 388 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 2 ms 788 KB Output is correct
8 Correct 2 ms 788 KB Output is correct
9 Correct 2 ms 788 KB Output is correct
10 Correct 2 ms 788 KB Output is correct
11 Correct 14 ms 2540 KB Output is correct
12 Correct 13 ms 2540 KB Output is correct
13 Correct 80 ms 8688 KB Output is correct
14 Correct 510 ms 34668 KB Output is correct
15 Correct 723 ms 34668 KB Output is correct
16 Correct 412 ms 34680 KB Output is correct
17 Correct 589 ms 34776 KB Output is correct
18 Correct 309 ms 34776 KB Output is correct
19 Execution timed out 3093 ms 145236 KB Time limit exceeded
20 Halted 0 ms 0 KB -