結果

問題 No.1896 Arrays and XOR Procedure 2
コンテスト
ユーザー tnakao0123
提出日時 2022-04-09 01:47:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,595 bytes
コンパイル時間 449 ms
コンパイル使用メモリ 50,636 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 19:53:54
合計ジャッジ時間 5,133 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 1 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1896.cc:  No.1896 Arrays and XOR Procedure 2 - yukicoder
 */

#include<cstdio>
#include<algorithm>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 3000;
const int MAX_K = 10000;

enum { OPA = 1, OPB = 2 };

/* typedef */

typedef pair<int,int> pii;

struct Op {
  int t, p, q;
  Op() {}
  Op(int _t, int _p, int _q): t(_t), p(_p), q(_q) {}
  void print() { printf("%d %d %d\n", t, p + 1, q + 1); }
};

/* global variables */

int as[MAX_N], bs[MAX_N];
Op ops[MAX_K];

/* subroutines */

pii getmsb(int n, int v[]) {
  int msb = 1, x = -1;
  for (int i = 0; i < n; i++) {
    while ((msb << 1) <= v[i]) msb <<= 1;
    if (v[i] & msb) x = i;
  }
  return pii(msb, x);
}

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", as + i);
  for (int i = 0; i < n; i++) scanf("%d", bs + i);

  pii pa = getmsb(n, as), pb = getmsb(n, as);
  int amsb = pa.first, ax = pa.second;
  int bmsb = pb.first, bx = pb.second;

  int k = 0;
  if (amsb < bmsb) {
    ops[k++] = Op(OPA, ax, bx);
    amsb = bmsb;
    as[ax] ^= bs[bx];
  }

  for (int i = 0; i < n; i++)
    if (! (bs[i] & amsb)) {
      ops[k++] = Op(OPB, ax, i);
      bs[i] ^= as[ax];
    }

  for (int i = 0; i < n; i++)
    if (as[i] & amsb) {
      ops[k++] = Op(OPB, i, 0);
      as[i] ^= bs[0];
    }

  printf("%d\n", k);
  for (int i = 0; i < k; i++) ops[i].print();

  if (false) {
    int maxa = *max_element(as, as + n);
    int minb = *min_element(bs, bs + n);
    if (maxa < minb) puts("OK");
    else puts("NG");
  }
  return 0;
}
0