oj.uz

Submission #49861

# Submission time Handle Problem Language Result Execution time Memory
49861 2018-06-04T00:27:58 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 173196 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];
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;
    f0(j, n){
        if(!bit(s, j)){
            if(s > 0){
                if(t[i + 1] != t[j + 1] && b[i + 1] != b[j + 1]) continue;
                ans = ans + calc(s | (1 << j), j);
            }
            else if(s==0){
                ans = ans + calc(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;
        }
    }
    cout << calc(0, 0);
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 172688 KB Output is correct
2 Correct 122 ms 172784 KB Output is correct
3 Correct 129 ms 172888 KB Output is correct
4 Correct 125 ms 172912 KB Output is correct
5 Correct 122 ms 172912 KB Output is correct
6 Correct 142 ms 172912 KB Output is correct
7 Correct 131 ms 172924 KB Output is correct
8 Correct 127 ms 172932 KB Output is correct
9 Correct 166 ms 172980 KB Output is correct
10 Correct 137 ms 173136 KB Output is correct
11 Correct 142 ms 173136 KB Output is correct
12 Correct 140 ms 173136 KB Output is correct
13 Correct 227 ms 173136 KB Output is correct
14 Correct 625 ms 173184 KB Output is correct
15 Correct 652 ms 173188 KB Output is correct
16 Correct 515 ms 173188 KB Output is correct
17 Correct 629 ms 173196 KB Output is correct
18 Correct 472 ms 173196 KB Output is correct
19 Execution timed out 3059 ms 173196 KB Time limit exceeded
20 Halted 0 ms 0 KB -