[Codeforces 1151B] Dima and a Bad XOR

[Codeforces 1151B] Dima and a Bad XOR - 1600

문제 설명 : 

n by m 크기의 행렬이 주어진다. 행렬의 각 열에서 임의의 숫자를 하나씩 뽑아서 xor를 취한다. 그 결과가 0이 나오지 않는 경우가 있다면 각 열에서 몇 번째 수를 xor해야하는지 출력하고, 아니면 반드시 결과가 0이 나올 수 밖에 없는지 구하는 문제이다.

풀이 : 

xor연산의 간단한 특성을 알아야 한다. 

a ^ b =0 을 만족한다면 a = b도 반드시 만족한다. 

또한 a^b = 0 이고  b≠c라면, a^c ≠ 0 도 반드시 성립한다.

이 두 가지 성질을 가지고 문제를 풀자.

이 문제에서의 관건은 어떤 수들을 xor해야 0이 나오지 않게 만드냐이다. 처음에는 일단 각 열의 첫 번째 원소들(mat[i][1])을 xor를 취해보자. 만약 그 결과가 운좋게 0이 아닌 값이 나오면 그냥 그게 답이 된다. 그런데 당연히 0이 나올 수도 있다. 그렇다면 과연 어떤 수 들로 바꿔주어야 할까? 정답은 '아무 숫자로만 바꾸면 된다'이다. 위의 특성에서 언급했다시피 a^b = 0 이라면, b≠c를 만족하는 a^c ≠ 0 도 성립한다.. 그런데 또 여기서 각 열에서 등장하는 숫자가 단 하나밖에 없다면, 즉 다른 값을 취할 수 있는 선택지가 없다면 결과가 0이 나올 수 밖에 없다. 그래서 행렬의 각 열에서 첫 번째 원소와 다른 수가 단 하나라도 존재한다면 0이 아닌 값을 반드시 만들 수 있고, 모든 열에서 단 하나의 수 밖에 등장하지 않는다면 불가능하다.

주의할 점 : 

-

배운 점 : 

xor의 신기한 특징을 배웠다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
/*********************Contest Template***********************/
const int SIZE= 509;
int mat[SIZE][SIZE];
int ans[SIZE];
 
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    exm="NIE";
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            scanf("%d",&mat[i][j]);
        }
    }
    for(int i=1 ; i<=n ; i++) ans[i]=1;
 
    int sum=0;
    pii diff={0,0};
    for(int i=1 ; i<=n ; i++){
        int first=mat[i][1];
        for(int j=2 ; j<=m ; j++){
            if(first!=mat[i][j]) diff={i,j};
        }
        sum ^= first;
    }
    if(sum==0){
        if(diff.first==0) exf();
        ans[diff.first]=diff.second;
    }
    printf("TAK\n");
    for(int i=1 ; i<=n ; i++)
        printf("%d ",ans[i]);
    return 0;
}