oj.uz

Submission #673815

# Submission time Handle Problem Language Result Execution time Memory
673815 2022-12-22T05:44:33 Z smartmonky Beautiful row (IZhO12_beauty) C++14
0 / 100
 273 ms 262144 KB 
#include <bits/stdc++.h>
 
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
//void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
const int N =  (1 << 21) + 1;
long long dp[N][21];
int a[21], bit[21], ter[21];
long long ful;
int getbits(int x){
	int res = 0;
	while(x > 0){
		res += x % 2;
		x >>= 1;
	}
	return res;
}
int getter(int x){
	int res = 0;
	while(x > 0){
		res += (x % 3 == 1);
		x /= 3;
	}
	return res;
}
 
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		ful += (1 << i);
		cin >> a[i];
		bit[i] = getbits(a[i]);
		ter[i] = getter(a[i]);
		dp[(1 << i)][i] = 1;
	}
	for(int i = 1; i < (1 << (n + 1)); i++){
		for(int j = 1; j <= n; j++){
			if(dp[i][j] == 0 ||  (i  & (1 << j)) == 0)continue;
				for(int k = 1; k  <= n; k++){
					if((i & (1 << k)))continue;
					if(bit[k] == bit[j] || ter[k] == ter[j] && i + (1 << k) <= ful)
						dp[i + (1 << k)][k] += dp[i][j];
				}
		}
	}
	long long ans = 0;
	for(int i = 1;  i <= n; i++){
		ans += dp[ful][i];
	}
	cout << ans;
}

Compilation message

beauty.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main(){
      | ^~~~
beauty.cpp: In function 'int main()':
beauty.cpp:51:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |      if(bit[k] == bit[j] || ter[k] == ter[j] && i + (1 << k) <= ful)
      |                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 9 ms 5460 KB Output is correct
12 Correct 7 ms 5588 KB Output is correct
13 Correct 36 ms 21824 KB Output is correct
14 Correct 173 ms 86476 KB Output is correct
15 Correct 158 ms 86492 KB Output is correct
16 Correct 159 ms 86480 KB Output is correct
17 Correct 196 ms 86388 KB Output is correct
18 Correct 148 ms 86472 KB Output is correct
19 Runtime error 273 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -