oj.uz

Submission #1017923

# Submission time Handle Problem Language Result Execution time Memory
1017923 2024-07-09T11:32:53 Z LM1 Beautiful row (IZhO12_beauty) C++14
100 / 100
 427 ms 180864 KB 
#include<bits/stdc++.h>
#define bin __builtin_popcount 
#define ll long long
#define int long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const int N=22;
int fix[N][N],dp[(1<<N)][N];
int ter(int x){
    int aa=0;
    while(x>0){
    	if(x%3==1)aa++;
        x/=3;
    }
    return aa;
}
main(){
    int n;cin>>n;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(bin(a[i])==bin(a[j])){
                fix[i][j]=1;
				fix[j][i]=1;
                continue;
            }
            if(ter(a[i])==ter(a[j])){
                fix[i][j]=1;
				fix[j][i]=1;
                continue;
            }
        }
    }
    int ans=0;
    for(int i=1;i<(1<<n);i++){
        vector<int>v;
        for(int j=0;j<n;j++)if((1<<j)&i)v.pb(j);
        if(bin(i)==1){
			dp[i][v[0]]=1;
			continue;
		}
        for(int j=0;j<v.size();j++){
			int l=v[j];
            for(int k=0;k<v.size();k++){
				int l1=v[k];
                if(j==k)continue;
                if(fix[l][l1])dp[i][l]+=dp[i^(1<<l)][l1];
            }
            if(i==(1<<n)-1)ans+=dp[i][l];
        }
    }
    cout<<ans;
}

Compilation message

beauty.cpp:19:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main(){
      | ^~~~
beauty.cpp: In function 'int main()':
beauty.cpp:45:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0;j<v.size();j++){
      |                     ~^~~~~~~~~
beauty.cpp:47:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for(int k=0;k<v.size();k++){
      |                         ~^~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Correct 4 ms 4700 KB Output is correct
13 Correct 16 ms 12940 KB Output is correct
14 Correct 79 ms 45396 KB Output is correct
15 Correct 77 ms 45392 KB Output is correct
16 Correct 82 ms 45392 KB Output is correct
17 Correct 86 ms 45452 KB Output is correct
18 Correct 94 ms 45392 KB Output is correct
19 Correct 427 ms 180776 KB Output is correct
20 Correct 356 ms 180864 KB Output is correct