oj.uz

Submission #83713

# Submission time Handle Problem Language Result Execution time Memory
83713 2018-11-10T05:43:28 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 165116 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)) & (1ll))

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

int n, a[N], b2[N], b3[N];
ll f[20][1ll << 20];

ll calc(int i, int s){
    if(f[i][s] != -1) return f[i][s];
    if(s==(1ll << (n)) - 1){
        f[i][s] = 1;
        return 1;
    }
    ll ans = 0;
    for(int j = 0; j < n; j++){
        if(bit(s, j)) continue;
        if(b2[i + 1] != b2[j + 1] && b3[i + 1] != b3[j + 1]) continue;
        ans = ans + calc(j, s + (1ll << j));
    }
    f[i][s] = ans;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n;
    f1(i, n){
        cin >> a[i];
        b2[i] = __builtin_popcount(a[i]);
        while(a[i]){
            int x = a[i]%3;
            b3[i] += (x==1);
            a[i] /= 3;
        }
    }
    memset(f, -1, sizeof(f));
    ll ans = 0;
    f1(i, n) ans = ans + calc(i - 1, (1ll << (i - 1)));

    cout << ans;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 164600 KB Output is correct
2 Correct 131 ms 164604 KB Output is correct
3 Correct 137 ms 164824 KB Output is correct
4 Correct 134 ms 164824 KB Output is correct
5 Correct 129 ms 164824 KB Output is correct
6 Correct 136 ms 164824 KB Output is correct
7 Correct 132 ms 164824 KB Output is correct
8 Correct 133 ms 164824 KB Output is correct
9 Correct 137 ms 164824 KB Output is correct
10 Correct 140 ms 164824 KB Output is correct
11 Correct 143 ms 164824 KB Output is correct
12 Correct 145 ms 164824 KB Output is correct
13 Correct 198 ms 164832 KB Output is correct
14 Correct 578 ms 165088 KB Output is correct
15 Correct 681 ms 165088 KB Output is correct
16 Correct 477 ms 165088 KB Output is correct
17 Correct 630 ms 165116 KB Output is correct
18 Correct 430 ms 165116 KB Output is correct
19 Execution timed out 3049 ms 165116 KB Time limit exceeded
20 Halted 0 ms 0 KB -