Submission #1178925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178925		Kanon	Bit Shift Registers (IOI21_registers)	C++20	0 / 100	1 ms	584 KiB

registers

#include <bits/stdc++.h>
#include "registers.h"

using namespace std;

const int b = 2000;
const int m = 100;
vector<bitset<b>> r(m);
int cnt = 0;

int so_far = 0;

void Move(int t, int y) {
  r[t] = r[y];
	so_far++;
}

int Store(vector<bool> v) {
  so_far++;
  int t = cnt++;
  assert(int(v.size()) == b);
  append_store(t, v);
  for (int i = 0; i < b; i++) r[t][i] = v[i];
  return t;
}
int And(int x, int y) {
  so_far++;
  int t = cnt++;
  append_and(t, x, y);
  r[t] = r[x] & r[y];
  return t;
}
int Or(int x, int y) {
  so_far++;
  int t = cnt++;
  append_or(t, x, y);
  r[t] = r[x] | r[y];
  return t;
}
int Xor(int x, int y) {
  so_far++;
  int t = cnt++;
  append_xor(t, x, y);
  r[t] = r[x] ^ r[y];
  return t;
}
int Not(int x) {
  so_far++;
  int t = cnt++;
  append_not(t, x);
  for (int i = 0; i < b; i++) r[t][i] = r[x][i] ? 0 : 1;
  return t;
}
int Shift_left(int x, int p) {
  so_far++;
  int t = cnt++;
  append_left(t, x, p);
  r[t] = r[x] << p;
  return t;
}
int Shift_right(int x, int p) {
  so_far++;
  int t = cnt++;
  append_right(t, x, p);
  r[t] = r[x] >> p;
  return t;
}
int Add(int x, int y) {
  so_far++;
  int t = cnt++;
  append_add(t, x, y);
  int carries = 0;
  for (int i = 0; i < b; i++) {
    int sum = r[x][i] + r[y][i] + carries;
    r[t][i] = sum % 2;
    carries = sum / 2;
  }
  return t;
}

struct Bitset {
  int id = -1;
  Bitset(int _id) : id(_id) {};
  Bitset operator-() const { return Bitset(Not(id)); };
  Bitset operator>>(int p) { return Bitset(Shift_right(id, p)); };
  Bitset operator<<(int p) { return Bitset(Shift_left(id, p)); };
  void operator=(const Bitset &a) { Move(id, a.id); };
};

Bitset operator+(const Bitset &lhs, const Bitset &rhs) { return Bitset(Add(lhs.id, rhs.id)) ;}
Bitset operator^(const Bitset &lhs, const Bitset &rhs) { return Bitset(Xor(lhs.id, rhs.id)) ;}
Bitset operator|(const Bitset &lhs, const Bitset &rhs) { return Bitset(Or(lhs.id, rhs.id)) ;}
Bitset operator&(const Bitset &lhs, const Bitset &rhs) { return Bitset(And(lhs.id, rhs.id)) ;}
Bitset Store(const function<bool(const int&)> &f) {
  vector<bool> bits(b);
  for (int i = 0; i < b; i++) bits[i] = f(i);
  return Bitset(Store(bits));
}

void construct_instructions(int s, int n, int k, int q) {
  Bitset a = Bitset(0);
  cnt++;
  Bitset Full = Store([&](int i) {
    return true;
  });
  Bitset One = Store([&](int i) {
    return i == 0;
  });
  int reset_register = cnt;
  auto Lesser_greater = [&](Bitset Even_skipped_blocks, Bitset Odd_skipped_blocks, int total_blocks) {
    assert(total_blocks & 1);
    Bitset Full_even_indexes = Store([&](int i) {
      int block_id = i / k;
      if (block_id >= total_blocks) return false;
      if (block_id & 1) return false;
      return true;
    });
    Bitset Header_remainder_even_blocks = Store([&](int i) {
      int block_id = i / k;
      if (block_id >= total_blocks + 1) return false;
      if (i % (2 * k) == k) return true;
      return false;
    });
    Bitset Even_plus_full_minus_odd = Even_skipped_blocks + (Full_even_indexes ^ Odd_skipped_blocks);
    Bitset Greater_even_blocks_head = Even_plus_full_minus_odd & Header_remainder_even_blocks;
    Bitset Full_greater_even_blocks = Greater_even_blocks_head + (Full ^ Greater_even_blocks_head >> k) + One;
    Bitset Full_not_less_odd_blocks = Full_greater_even_blocks ^ Full_even_indexes;
    Bitset Greater_skipped = (Even_skipped_blocks & Full_greater_even_blocks) ^ (Odd_skipped_blocks & Full_not_less_odd_blocks);
    Bitset Lesser_skipped = Even_skipped_blocks ^ Odd_skipped_blocks ^ Greater_skipped;
    Bitset ret = Lesser_skipped ^ (Greater_skipped << k);
    return ret;
  };
  auto E_O_switch = [&]() {
    Bitset Even_skipped_blocks = a & Store([&](int i) {
      if (i >= n * k) return false;
      int block_id = i / k;
      return block_id % 2 == 0;
    });
    Bitset Odd_skipped_blocks = (a & Store([&](int i) {
      if (i >= n * k) return false;
      int block_id = i / k;
      return block_id % 2 == 1;
    })) >> k;
    int last_even_block_id = n - 1 - (n & 1 ^ 1);
    int last_odd_block_id = n - 1 - (n & 1);
    int total_block = last_even_block_id + 1;
    if (last_odd_block_id != total_block) Odd_skipped_blocks = Odd_skipped_blocks | Store([&](int i) {
      int L = (total_block - 1) * k, R = L + k - 1;
      return L <= i && i <= R;
    });
    a = Lesser_greater(Even_skipped_blocks, Odd_skipped_blocks, total_block);
    if (last_odd_block_id != total_block) a = a ^ Store([&](int i) {
      int L = total_block * k + k, R = L + k - 1;
      return L <= i && i <= R;
    });
    cnt = reset_register;
  };
  auto O_E_switch = [&]() {
    if (n <= 2) return;
    Bitset Even_skipped_blocks = (a & Store([&](int i) {
      if (i >= n * k) return false;
      int block_id = i / k;
      return block_id % 2 == 0;
    })) >> (k << 1);
    Bitset Odd_skipped_blocks = (a & Store([&](int i) {
      if (i >= n * k) return false;
      int block_id = i / k;
      return block_id % 2 == 1;
    })) >> k;
    int last_even_block_id = n - 1 - (n & 1 ^ 1);
    int last_odd_block_id = n - 1 - (n & 1);
    int total_block = last_odd_block_id;
    if (last_even_block_id != total_block + 1) Even_skipped_blocks = Even_skipped_blocks | Store([&](int i) {
      int L = (total_block - 1) * k, R = L + k - 1;
      return L <= i && i <= R;
    });
    Bitset first_block = a & Store([&](int i) {
      return i < k;
    });
    a = Lesser_greater(Odd_skipped_blocks, Even_skipped_blocks, total_block) << k | first_block;
    if (last_odd_block_id != total_block) a = a ^ Store([&](int i) {
      int L = (total_block + 1) * k + k, R = L + k - 1;
      return L <= i && i <= R;
    });
    cnt = reset_register;
  };
  if (s == 1) {
    int beg = 0;
    int iter = n;
    while (iter--) {
      if (!beg & 1) {
        E_O_switch();
      } else {
        O_E_switch();
      }
      beg ^= 1;
    }
    assert(so_far <= q);
  } else {
    Bitset Full_even_indexes = Store([&](int i) {
      int block_id = i / k;
      if (block_id & 1) return false;
      return true;
    });
    Bitset Header_remainder_even_blocks = Store([&](int i) {
      int block_id = i / k;
      if (i % (2 * k) == k) return true;
      return false;
    });
    auto Lesser = [&](Bitset Even_skipped_blocks, Bitset Odd_skipped_blocks) {
      Bitset Even_plus_full_minus_odd = Even_skipped_blocks + (Full_even_indexes ^ Odd_skipped_blocks);
      Bitset Greater_even_blocks_head = Even_plus_full_minus_odd & Header_remainder_even_blocks;
      Bitset Full_greater_even_blocks = Greater_even_blocks_head + (Full ^ Greater_even_blocks_head >> k) + One;
      Bitset Full_not_less_odd_blocks = Full_greater_even_blocks ^ Full_even_indexes;
      Bitset Lesser_skipped = (Even_skipped_blocks & Full_not_less_odd_blocks) ^ (Odd_skipped_blocks & Full_greater_even_blocks);
      return Lesser_skipped;
    };
    a = a | Store([&](int i) {
      return n * k <= i;
    });
    Bitset Even_skipped_blocks = a & Full_even_indexes;
    Bitset Odd_skipped_blocks = (a & Full_even_indexes << k) >> k;
    Bitset Lesser_skipped = Lesser(Even_skipped_blocks, Odd_skipped_blocks);
    int Log = 1;
    while ((1 << Log) - 1 < n - 1) {
      Lesser_skipped = Lesser(Lesser_skipped, Lesser_skipped >> (k << Log));
      Log++;
    }
    a = Lesser_skipped;
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29