oj.uz

Submission #83715

# Submission time Handle Problem Language Result Execution time Memory
83715 2018-11-10T05:53:56 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 263168 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++)

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

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

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;
    }
    ///int cur = (1ll << n) - 1 - s;
    ll ans = 0;
    ///for(; state > 0; state ^= state & -state){
    for(auto j:v[s]){
        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;
        }
    }
    v.resize((1ll << n));
    f0(i, (1ll << n)){
        f0(j, n){
            if((i >> j)&1) continue;
            v[i].emplace_back(j);
        }
    }
    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 134 ms 164472 KB Output is correct
2 Correct 142 ms 164472 KB Output is correct
3 Correct 142 ms 164492 KB Output is correct
4 Correct 134 ms 164556 KB Output is correct
5 Correct 143 ms 164556 KB Output is correct
6 Correct 142 ms 164608 KB Output is correct
7 Correct 132 ms 164624 KB Output is correct
8 Correct 143 ms 164664 KB Output is correct
9 Correct 138 ms 164704 KB Output is correct
10 Correct 140 ms 164736 KB Output is correct
11 Correct 149 ms 165888 KB Output is correct
12 Correct 150 ms 166072 KB Output is correct
13 Correct 296 ms 170052 KB Output is correct
14 Correct 783 ms 187880 KB Output is correct
15 Correct 1010 ms 187956 KB Output is correct
16 Correct 691 ms 187956 KB Output is correct
17 Correct 881 ms 187956 KB Output is correct
18 Correct 598 ms 188052 KB Output is correct
19 Execution timed out 3044 ms 263168 KB Time limit exceeded
20 Halted 0 ms 0 KB -