結果

問題 No.5001 排他的論理和でランニング
ユーザー pekempey
提出日時 2018-03-16 23:51:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,978 bytes
コンパイル時間 842 ms
実行使用メモリ 19,096 KB
スコア 0
最終ジャッジ日時 2020-03-12 19:40:29
ジャッジサーバーID
（参考情報） 		judge7 /
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>

using namespace std;

const int N = 1e5;

int n, m;
int a[N];
vector<int> used[N];

vector<int> merge(vector<int> a, vector<int> b) {
  map<int, int> mp;
  for (int x : a) mp[x]++;
  for (int x : b) mp[x]++;
  vector<int> res;
  for (auto kv : mp) {
    if (kv.second % 2 == 1) {
      res.push_back(kv.first);
    }
  }
  return res;
}

void swap_row(int i, int j) {
  swap(a[i], a[j]);
  swap(used[i], used[j]);
}

// i -> j
void add_row(int i, int j) {
  a[j] ^= a[i];
  used[j] = merge(used[i], used[j]);
}

int gauss() {
  int r = 0;
  for (int j = 20; j >= 0; j--) {
    int p = -1;
    for (int i = r; i < n; i++) {
      if (a[i] >> j & 1) {
        p = i;
        break;
      }
    }
    if (p == -1) continue;
    swap_row(r, p);
    for (int i = r + 1; i < n; i++) {
      if (a[i] >> j & 1) {
        add_row(r, i);
      }
    }
    r++;
  }
  return r;
}

void answer(vector<int> a) {
  for (int i = 0; i < a.size(); i++) {
    if (i > 0) cout << ' ';
    cout << a[i] + 1;
  }
  cout << endl;
  exit(0);
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    used[i].push_back(i);
  }
  int r = gauss();

  cerr << "rank " << r << endl;
  vector<int> res;
  int curr = 0;
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < used[i].size(); j++) {
      cerr << used[i][j] << ' ';
    }
    cerr << endl;
  }
  cerr << endl;
  for (int i = 0; i < r; i++) {
    auto next_res = merge(res, used[i]);
    if ((curr ^ a[i]) > curr && next_res.size() <= m) {
      curr ^= a[i];
      res = next_res;
    }
    if (res.size() == m) break;
  }
  cerr << curr << endl;
  if (res.size() == m) {
    answer(res);
  }
  cerr << res.size() << endl;
  for (int i = r; i < n; i++) {
    auto next_res = merge(res, used[i]);
    if (next_res.size() == m) {
      answer(next_res);
    }
    if (next_res.size() < m) {
      res = next_res;
    }
  }
}
0