結果

問題 No.1896 Arrays and XOR Procedure 2
コンテスト
ユーザー tnakao0123
提出日時 2022-04-09 01:58:56
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,733 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 402 ms
コンパイル使用メモリ 50,476 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-28 20:19:58
合計ジャッジ時間 3,922 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- 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, bs);
  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(OPA, 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);
    for (int i = 0; i < n; i++) printf("%d ", as[i]); putchar('\n');
    for (int i = 0; i < n; i++) printf("%d ", bs[i]); putchar('\n');
    if (maxa < minb) puts("OK");
    else puts("NG");
  }
  return 0;
}
0