oj.uz

Submission #83714

# Submission time Handle Problem Language Result Execution time Memory
83714 2018-11-10T05:49:38 Z mra2322001 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2697 ms 164972 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 log lr

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

int n, a[N], b2[N], b3[N];
int log[1ll << 20];
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;
    }
    int cur = (1ll << n) - 1 - s;

    ll ans = 0;
    ///for(; state > 0; state ^= state & -state){
    for(cur; cur > 0; cur ^= cur & -cur){
        int j = log[cur & -cur];
        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);

    f0(i, 20){
        log[1ll << i] = i;
    }
    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;
}

Compilation message

beauty.cpp: In function 'll calc(int, int)':
beauty.cpp:24:12: warning: statement has no effect [-Wunused-value]
     for(cur; cur > 0; cur ^= cur & -cur){
            ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 164600 KB Output is correct
2 Correct 138 ms 164724 KB Output is correct
3 Correct 134 ms 164724 KB Output is correct
4 Correct 138 ms 164768 KB Output is correct
5 Correct 139 ms 164768 KB Output is correct
6 Correct 136 ms 164768 KB Output is correct
7 Correct 136 ms 164768 KB Output is correct
8 Correct 136 ms 164768 KB Output is correct
9 Correct 134 ms 164768 KB Output is correct
10 Correct 137 ms 164768 KB Output is correct
11 Correct 143 ms 164768 KB Output is correct
12 Correct 137 ms 164768 KB Output is correct
13 Correct 179 ms 164768 KB Output is correct
14 Correct 431 ms 164768 KB Output is correct
15 Correct 505 ms 164884 KB Output is correct
16 Correct 376 ms 164884 KB Output is correct
17 Correct 491 ms 164972 KB Output is correct
18 Correct 357 ms 164972 KB Output is correct
19 Correct 2431 ms 164972 KB Output is correct
20 Correct 2697 ms 164972 KB Output is correct