oj.uz

Submission #49864

# Submission time Handle Problem Language Result Execution time Memory
49864 2018-06-04T00:38:15 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2786 ms 172984 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)
#define bit(x, y) (((x) >> (y))&1)

using namespace std;
typedef long long ll;
const int N = 21;

int n, a[N], t[N], b[N];
vector <int> y[N];
ll f[1 << 20][N];

ll calc(int s, int i){
    if(f[s][i] != -1) return f[s][i];
    if(s == (1 << n) - 1){
        f[s][i] = 1;
        return 1;
    }
    ll &ans = f[s][i];
    ans = 0;
    if(s==0){
        f0(j, n){
            ans = ans + calc(1 << j, j);
        }
    }
    if(s > 0){
        for(auto j:y[i]){
            if(bit(s, j)==0) ans = ans + calc(s | (1 << j), j);
        }
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
   
    memset(f, -1, sizeof(f));
    cin >> n;
    f1(i, n){
        cin >> a[i];
        b[i] = __builtin_popcount(a[i]);
        while(a[i]){
            int r = a[i]%3;
            if(r==1) t[i]++;
            a[i] /= 3;
        }
    }
    f1(i, n){
        f1(j, n){
            if(i != j){
                if(t[i]==t[j] || b[i]==b[j]){
                    y[i - 1].push_back(j - 1);
                }
            }
        }
    }
    cout << calc(0, 0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 172708 KB Output is correct
2 Correct 137 ms 172776 KB Output is correct
3 Correct 125 ms 172824 KB Output is correct
4 Correct 130 ms 172824 KB Output is correct
5 Correct 142 ms 172824 KB Output is correct
6 Correct 130 ms 172840 KB Output is correct
7 Correct 135 ms 172840 KB Output is correct
8 Correct 129 ms 172880 KB Output is correct
9 Correct 130 ms 172880 KB Output is correct
10 Correct 150 ms 172928 KB Output is correct
11 Correct 139 ms 172928 KB Output is correct
12 Correct 135 ms 172928 KB Output is correct
13 Correct 205 ms 172968 KB Output is correct
14 Correct 523 ms 172968 KB Output is correct
15 Correct 627 ms 172968 KB Output is correct
16 Correct 403 ms 172968 KB Output is correct
17 Correct 458 ms 172968 KB Output is correct
18 Correct 309 ms 172984 KB Output is correct
19 Correct 2620 ms 172984 KB Output is correct
20 Correct 2786 ms 172984 KB Output is correct