oj.uz

Submission #83716

# Submission time Handle Problem Language Result Execution time Memory
83716 2018-11-10T05:54: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 146 ms 164472 KB Output is correct
2 Correct 140 ms 164604 KB Output is correct
3 Correct 137 ms 164604 KB Output is correct
4 Correct 137 ms 164668 KB Output is correct
5 Correct 133 ms 164668 KB Output is correct
6 Correct 150 ms 164760 KB Output is correct
7 Correct 138 ms 164760 KB Output is correct
8 Correct 140 ms 164828 KB Output is correct
9 Correct 137 ms 164828 KB Output is correct
10 Correct 136 ms 164828 KB Output is correct
11 Correct 156 ms 165980 KB Output is correct
12 Correct 161 ms 165980 KB Output is correct
13 Correct 305 ms 170076 KB Output is correct
14 Correct 800 ms 188156 KB Output is correct
15 Correct 1027 ms 188156 KB Output is correct
16 Correct 730 ms 188156 KB Output is correct
17 Correct 888 ms 188156 KB Output is correct
18 Correct 602 ms 188156 KB Output is correct
19 Execution timed out 3052 ms 263168 KB Time limit exceeded
20 Halted 0 ms 0 KB -