oj.uz

Submission #946554

# Submission time Handle Problem Language Result Execution time Memory
946554 2024-03-14T18:27:56 Z sondos225 Beautiful row (IZhO12_beauty) C++17
100 / 100
 2975 ms 172888 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
int m2[20];
int m3[20];
int n;
int dp[21][(1<<20)];
int dfs(int x, int mask)
{
   if (mask==((1<<n)-1)) return 1;
   if (dp[x][mask]!=-1) return dp[x][mask];
   int c=0;
   forr(i,0,n)
   {
       if (m2[x]==m2[i] || m3[x]==m3[i]){
       if (!((1<<i)&mask))
       {
          // mask|=;
           c+=dfs(i,(mask|(1<<i)));
         //  mask^=(1<<i);
       }
       }
   }
   return dp[x][mask]=c;
}
signed main()
{
//    #ifndef LOCAL
//    freopen("lifeguards.in","r",stdin);
//    freopen("lifeguards.out","w", stdout);
//    #endif
    fast
   // int n;
    cin>>n;
    int a[n];
    mms(dp,-1);
    forr(i,0,n)
    {
        cin>>a[i];
        int x=a[i];
        while(x>0)
        {
            if (x%2==1) m2[i]++;
            x/=2;
        }
        x=a[i];
        while(x>0)
        {
            if (x%3==1) m3[i]++;
            x/=3;
        }
    }
    int ans=0;
    forr(i,0,n)
    {
        ans+=dfs(i,(1<<i));
    }
    cout<<ans;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 172624 KB Output is correct
2 Correct 22 ms 172632 KB Output is correct
3 Correct 21 ms 172636 KB Output is correct
4 Correct 21 ms 172692 KB Output is correct
5 Correct 24 ms 172672 KB Output is correct
6 Correct 21 ms 172616 KB Output is correct
7 Correct 22 ms 172628 KB Output is correct
8 Correct 21 ms 172636 KB Output is correct
9 Correct 21 ms 172636 KB Output is correct
10 Correct 21 ms 172788 KB Output is correct
11 Correct 29 ms 172624 KB Output is correct
12 Correct 30 ms 172712 KB Output is correct
13 Correct 63 ms 172796 KB Output is correct
14 Correct 317 ms 172632 KB Output is correct
15 Correct 401 ms 172796 KB Output is correct
16 Correct 301 ms 172632 KB Output is correct
17 Correct 350 ms 172888 KB Output is correct
18 Correct 198 ms 172636 KB Output is correct
19 Correct 2476 ms 172796 KB Output is correct
20 Correct 2975 ms 172880 KB Output is correct