Submission #978769

#	Time	Username	Problem	Language	Result	Execution time	Memory
978769		AdamGS	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	1 ms	604 KiB

registers

#include "registers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int B=2000;
void construct_minimum(int n, int k) {
  vector<bool>T(B);
  for(int i=1; i<n; i*=2) {
    rep(j, B) T[j]=0;
    for(int j=0; j<n; j+=2*i) rep(l, k) T[j*k+l]=1;
    append_store(1, T);
    rep(j, B) T[j]=0;
    for(int j=i; j<n; j+=2*i) rep(l, k) T[j*k+l]=1;
    append_store(2, T);
    rep(j, B) T[j]=0;
    for(int j=0; j<n; j+=2*i) {
      rep(l, k) T[j*k+l]=1;
      if(j+i<n) rep(l, k) T[j*k+k+l]=1;
    }
    append_store(12, T);
    append_and(3, 0, 1);
    append_and(4, 0, 2);
    append_right(5, 4, k*i);
    append_not(6, 3);
    append_add(7, 5, 6);
    append_xor(8, 3, 5);
    append_left(9, 8, k);
    append_and(10, 7, 9);
    append_and(10, 10, 12);
    append_right(11, 10, k);
    append_xor(0, 0, 11);
  }
}
void construct_instructions(int s, int n, int k, int q) {
  if(s==0) {
    construct_minimum(n, k);
    return;
  }
  vector<bool>T(B);
  for(int i=0; i<n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(1, T); // 10101010
  rep(i, B) T[i]=0; 
  for(int i=1; i<n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(2, T); // 01010101
  rep(i, B) T[i]=0;
  for(int i=0; i<=n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(12, T);
  rep(i, B) T[i]=0;
  for(int i=1; i<=n; i+=2) rep(j, k) T[i*k+j]=1;
  append_store(13, T);
  rep(i, B) T[i]=0;
  rep(i, n*k) T[i]=1;
  append_store(14, T);
  rep(i, B) T[i]=0;
  rep(i, (n+1)*k) T[i]=1;
  append_store(15, T);
  rep(i, n) {
    if(i%2==0) {
      append_and(3, 0, 1); // a0 0 a2 0 a4 ... an 0
      append_and(4, 0, 2); // 0 a1 0 a3 0 ... 0 a(n-1)
    } else {
      append_left(0, 0, k);
      append_and(3, 0, 12);
      append_and(4, 0, 13);
    }
    append_right(5, 4, k); // a1 0 a3 0 ... a(n-1) 0
    append_not(6, 3); // a0' 1 a2' 1 a4' ... an' 1
    append_add(7, 5, 6);
    append_xor(8, 3, 5);
    append_left(9, 8, k);
    append_and(10, 7, 9);
    append_and(10, 10, 14+(i%2));
    append_xor(0, 0, 10);
    append_right(11, 10, k);
    append_xor(0, 0, 11);
    if(i%2==1) append_right(0, 0, k);
  }
}

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