R618(Div.2) C. Anu Has a Function

 

수학 공부 열심히 한다는 마음으로 항상 틀리며 공부하고있다 ㅎㅎ

이 문제를 풀 때 혼자 너무 어렵게 접근해서 처음에는 반도 못갔다

코포 끝나고 혼자 풀어보니까 f(a,b) = a&(-b) 로 정리된다는걸 깨달았다

근데 거기서 발전은 못해서 에디토리얼을 봤다 ㅎㅎ 어렵다..!!

 

결국 a1~an까지 정리하면 a1&(-a2)&(-a3)&(-a4)...&(-an)이 된다는 걸 알 수 있다

 

그럼 여기서 주목할 건 내가 어떤 2^k 승의 비트를 가지는 수가 1개라면

그걸 a1에 놨을 때 나머지 a2~an까지 -가 붙기 때문에 2^k 위치를 살려준다!

 

예를들어 2^5 비트가 1인 수가 딱 1개만 있고 그걸 a1에 둔다면

나머지 수들은 2^5가 0이지만 -가 붙어서 1로변하고 a1에 놓인 2^5가 계속 1일 수 있다

 

그렇다면 우린 비트별로 수를 세서 가장 큰 곳부터 보면서 내려오고

그 중에 수가 1개인게 있다면 그걸 출력하고 나머지는 그냥 쭉 출력하면 된다

 

없다면 답은 그냥 0이다!

 

같은 비트의 수가 2개 이상이라면 &연산에서 결국 0이 될 것이다

 

이런걸 대체 어떻게 생각하는걸까..! 어렵다어렵다어렵당럽뎌ㅏ

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> bit[32];
int n;
int arr[100010];
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n;i++){
        int x; scanf(" %d",&x);
        arr[i]=x;
        for(int j=0;j<30;j++){
            if(x&(1<<j)) bit[j].push_back(i);
        }
    }
 
    for(int i=30;i>=0;i--){
        if(bit[i].size()==0) continue;
        if(bit[i].size()==1){
            int now = bit[i][0];
            printf("%d ",arr[now]); 
            for(int j=0;j<n;j++){
                if(now==j) continue;
                printf("%d ",arr[j]);
            }
            return 0;
        }
    }
    for(int i=0;i<n;i++) printf("%d ",arr[i]); 
}