oj.uz

Submission #49862

# Submission time Handle Problem Language Result Execution time Memory
49862 2018-06-04T00:32:40 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 173040 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;
    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;
    }
    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 127 ms 172664 KB Output is correct
2 Correct 130 ms 172920 KB Output is correct
3 Correct 125 ms 172920 KB Output is correct
4 Correct 129 ms 172920 KB Output is correct
5 Correct 126 ms 172920 KB Output is correct
6 Correct 143 ms 172920 KB Output is correct
7 Correct 138 ms 172920 KB Output is correct
8 Correct 127 ms 172920 KB Output is correct
9 Correct 129 ms 172920 KB Output is correct
10 Correct 136 ms 172920 KB Output is correct
11 Correct 145 ms 172920 KB Output is correct
12 Correct 152 ms 172920 KB Output is correct
13 Correct 217 ms 173040 KB Output is correct
14 Correct 595 ms 173040 KB Output is correct
15 Correct 714 ms 173040 KB Output is correct
16 Correct 503 ms 173040 KB Output is correct
17 Correct 668 ms 173040 KB Output is correct
18 Correct 456 ms 173040 KB Output is correct
19 Correct 2914 ms 173040 KB Output is correct
20 Execution timed out 3052 ms 173040 KB Time limit exceeded