ぬるぬるの競プロ日記

コードをぬるぬる書きたいです。

AtCoder Beginner Contest 126 F - XOR Matching

考えたこと:

・値の等しい任意のai,ajに対して題意の条件が成立するので、構築できるならば対称性がありそう。

 

・もしかして、K==0の場合にしか構築できないのでは??

ー>場合分けして提出。

ー>そんなことなかった。

 

・紙上で実験をし続けていると、どうやら

 

ABC・・・X K X・・・CBA K

というパターンが条件を満たしそうであるということがわかった。

 

満たさなければいけない条件は

X・・・CBA のxorがKと等しくなる。ことである。

 

実装:

#include <bits/stdc++.h>
using namespace std;
#define int long long

int M, K;

signed main() {
  cin >> M >> K;
  if (M == 0) {
    if (K == 0) {
      cout << 0 << " " << 0 << endl;
    } else {
      cout << -1 << endl;
    }
    return 0;
  }

  if ((1 << M) <= K) {
    cout << -1 << endl;
    return 0;
  }

  if (K == 0) {
    for (int i = 0; i < (1 << (M + 1)); i++) {
      if (i != 0) cout << " ";
      cout << i / 2;
    }
    cout << endl;
    return 0;
  }

  int tmp = 0;
  for (int i = 0; i < (1 << M); i++) {
    if (i != K) tmp ^= i;
  }

  if (tmp != K) {
    cout << -1 << endl;
    return 0;
  }

  vector<int> v;
  for (int i = 0; i < (1 << M); i++) {
    if (i != K) v.push_back(i);
  }
  vector<int> rev = v;
  reverse(rev.begin(), rev.end());
  v.push_back(K);
  rev.push_back(K);

  for (auto x : v) cout << x << " ";
  for (int i = 0; i < rev.size(); i++) {
    if (i != 0) cout << " ";
    cout << rev[i];
  }
  cout << endl;

  return 0;
}

 

感想

構築が苦手だったので解けて良かったです。

(少し好きになりました。)

 

全体としては全完できました。

高揚感がありました。楽しかったです。