oj.uz

답안 #83717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83717 2018-11-10T05:55:42 Z mra2322001 아름다운 순열 (IZhO12_beauty) C++14
100 / 100
 2660 ms 164948 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

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 164604 KB Output is correct
2 Correct 138 ms 164740 KB Output is correct
3 Correct 140 ms 164808 KB Output is correct
4 Correct 138 ms 164808 KB Output is correct
5 Correct 135 ms 164808 KB Output is correct
6 Correct 142 ms 164808 KB Output is correct
7 Correct 140 ms 164808 KB Output is correct
8 Correct 135 ms 164808 KB Output is correct
9 Correct 140 ms 164808 KB Output is correct
10 Correct 137 ms 164808 KB Output is correct
11 Correct 163 ms 164808 KB Output is correct
12 Correct 155 ms 164808 KB Output is correct
13 Correct 187 ms 164820 KB Output is correct
14 Correct 434 ms 164820 KB Output is correct
15 Correct 504 ms 164820 KB Output is correct
16 Correct 402 ms 164820 KB Output is correct
17 Correct 496 ms 164940 KB Output is correct
18 Correct 372 ms 164948 KB Output is correct
19 Correct 2446 ms 164948 KB Output is correct
20 Correct 2660 ms 164948 KB Output is correct