結果

問題 No.2195 AND Set
コンテスト
ユーザー chro_96
提出日時 2023-01-20 21:48:14
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 302 ms / 2,000 ms
コード長 2,087 bytes
コンパイル時間 1,374 ms
コンパイル使用メモリ 31,216 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2024-06-23 09:44:54
合計ジャッジ時間 6,290 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

int cmp_int_2d (const void *a, const void *b) {
  int *a_ = (int *)a;
  int *b_ = (int *)b;
  
  if (a_[0] < b_[0]) {
    return -1;
  }
  
  if (a_[0] > b_[0]) {
    return 1;
  }
  
  if (a_[1] < b_[1]) {
    return -1;
  }
  
  if (a_[1] > b_[1]) {
    return 1;
  }
  
  return 0;
}

int main () {
  int q = 0;
  int t[400000] = {};
  int x[400000] = {};
  
  int res = 0;
  
  int xit[400000][3] = {};
  int cnt[30] = {};
  int num = 0;
  
  res = scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    res = scanf("%d", t+i);
    if (t[i] == 1 || t[i] == 2) {
      res = scanf("%d", x+i);
    } else {
      x[i] = -1;
    }
    xit[i][0] = x[i];
    xit[i][1] = i;
    xit[i][2] = t[i];
  }
  
  qsort(xit, q, sizeof(int)*3, cmp_int_2d);
  for (int i = 0; i < q; i++) {
    if (t[i] == 1) {
      int idx[2] = { -1, q-1 };
      while (idx[1]-idx[0] > 1) {
        int nxt = (idx[0]+idx[1])/2;
        if (xit[nxt][0] < x[i] || (xit[nxt][0] == x[i] && xit[nxt][1] < i)) {
          idx[0] = nxt;
        } else {
          idx[1] = nxt;
        }
      }
      if (idx[0] < 0 || xit[idx[0]][0] != x[i] || xit[idx[0]][2] == 2) {
        for (int j = 0; j < 30; j++) {
          if ((x[i]&(1<<j)) > 0) {
            cnt[j]++;
          }
        }
        num++;
      }
    } else if (t[i] == 2) {
      int idx[2] = { -1, q-1 };
      while (idx[1]-idx[0] > 1) {
        int nxt = (idx[0]+idx[1])/2;
        if (xit[nxt][0] < x[i] || (xit[nxt][0] == x[i] && xit[nxt][1] < i)) {
          idx[0] = nxt;
        } else {
          idx[1] = nxt;
        }
      }
      if (idx[0] >= 0 && xit[idx[0]][0] == x[i] && xit[idx[0]][2] == 1) {
        for (int j = 0; j < 30; j++) {
          if ((x[i]&(1<<j)) > 0) {
            cnt[j]--;
          }
        }
        num--;
      }
    } else {
      int ans = 0;
      for (int j = 0; j < 30; j++) {
        if (cnt[j] == num) {
          ans += (1<<j);
        }
      }
      if (num > 0) {
        printf("%d\n", ans);
      } else {
        printf("-1\n");
      }
    }
  }
  
  return 0;
}
0