oj.uz

Submission #49863

# Submission time Handle Problem Language Result Execution time Memory
49863 2018-06-04T00:36:35 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2677 ms 173216 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(__builtin_popcount(s)==n-2){
        int h = -1, k = -1;
        f0(j, n){
            if(bit(s, j)==0){
                if(h==-1) h = j;
                else k = j;
            }
        }
        if(t[h + 1] != t[k + 1] && b[h + 1] != b[k + 1]) return 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 141 ms 172676 KB Output is correct
2 Correct 124 ms 172736 KB Output is correct
3 Correct 122 ms 172784 KB Output is correct
4 Correct 121 ms 172884 KB Output is correct
5 Correct 120 ms 172884 KB Output is correct
6 Correct 155 ms 172960 KB Output is correct
7 Correct 122 ms 172960 KB Output is correct
8 Correct 126 ms 172992 KB Output is correct
9 Correct 123 ms 173036 KB Output is correct
10 Correct 122 ms 173036 KB Output is correct
11 Correct 143 ms 173036 KB Output is correct
12 Correct 145 ms 173036 KB Output is correct
13 Correct 211 ms 173036 KB Output is correct
14 Correct 564 ms 173052 KB Output is correct
15 Correct 607 ms 173216 KB Output is correct
16 Correct 459 ms 173216 KB Output is correct
17 Correct 535 ms 173216 KB Output is correct
18 Correct 394 ms 173216 KB Output is correct
19 Correct 2283 ms 173216 KB Output is correct
20 Correct 2677 ms 173216 KB Output is correct