Submission #1178929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178929		Kanon	Bit Shift Registers (IOI21_registers)	C++20	Compilation error	0 ms	0 KiB

registers

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

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

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

vector<int> to_vec(int id, int n, int k) {
  vector<int> a(n);
  for (int i = 0; i < n * k; i++) {
    a[i / k] += r[id][i] << (i % k);
  }
  return a;
}

void Printf(int n, int k, int id) {
  vector<int> a = to_vec(id, n, k);
  cerr << "{";
  for (int i = 0; i < n; i++) {
    if (i != 0) cerr << " ";
    cerr << a[i];
    if (i != n - 1) cerr << ",";
  }
  cerr << "}";
  cerr << endl;
}

void append_move(int t, int y) {}
void append_store(int t, vector<bool> v) {}
void append_and(int t, int x, int y) {}
void append_or(int t, int x, int y) {}
void append_xor(int t, int x, int y) {}
void append_not(int t, int x) {}
void append_left(int t, int x, int p) {}
void append_right(int t, int x, int p) {}
void append_add(int t, int x, int y) {}

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));
}

int N, K;

void debug_out(Bitset a) {
  Printf(N, K, a.id);
}

void construct_instructions(int s, int n, int k, int q) {
  N = n, K = k;
  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) {
      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;
  }
  assert(so_far <= q);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_move(int, int)':
grader.cpp:(.text+0x420): multiple definition of `append_move(int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb00): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_store(int, std::vector<bool, std::allocator<bool> >)':
grader.cpp:(.text+0x5c0): multiple definition of `append_store(int, std::vector<bool, std::allocator<bool> >)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb10): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_and(int, int, int)':
grader.cpp:(.text+0x7f0): multiple definition of `append_and(int, int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb20): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_or(int, int, int)':
grader.cpp:(.text+0x9c0): multiple definition of `append_or(int, int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb30): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_xor(int, int, int)':
grader.cpp:(.text+0xb90): multiple definition of `append_xor(int, int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb40): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_not(int, int)':
grader.cpp:(.text+0xd60): multiple definition of `append_not(int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb50): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_left(int, int, int)':
grader.cpp:(.text+0xf00): multiple definition of `append_left(int, int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb60): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_right(int, int, int)':
grader.cpp:(.text+0x10d0): multiple definition of `append_right(int, int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb70): first defined here
/usr/bin/ld: /tmp/cc4H8O9o.o: in function `append_add(int, int, int)':
grader.cpp:(.text+0x12a0): multiple definition of `append_add(int, int, int)'; /tmp/ccRyRUpr.o:registers.cpp:(.text+0xb80): first defined here
collect2: error: ld returned 1 exit status