Submission #439924

#	Time	Username	Problem	Language	Result	Execution time	Memory
439924		cheeheng	Bit Shift Registers (IOI21_registers)	C++17	23 / 100	6 ms	1176 KiB

registers

#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

const int b1 = 2000;
const int ONE = 51; // address of the value 1

void append_subtract(int t, int x, int y){
    // 99 is the complement of y
    append_not(99, y);
    append_add(99, ONE, 99);

    append_add(t, x, 99);
    return;
}

void swap1(int x, int y, int k){
    vector<bool> andX(b1);
    for(int i = x*k; i < (x+1)*k; i ++){
        andX[i] = 1;
    }
    append_store(99, andX);

    vector<bool> andY(b1);
    for(int i = y*k; i < (y+1)*k; i ++){
        andY[i] = 1;
    }
    append_store(98, andY);

    append_and(97, 0, 99);
    append_and(96, 0, 98);

    append_right(97, 97, x*k); // value of x
    append_right(96, 96, y*k); // value of y

    append_subtract(95, 97, 96); // x-y
    append_right(94, 95, k); // if value of 94 is 111111..., then x <= y, otherwise, must swap
    append_not(94, 94); // if value of 94 is 111111..., then swap

    append_and(94, 50, 94); // only k 1s required

    append_and(93, 94, 95); // 93 should be zero if x <= y otherwise shows x-y

    append_subtract(97, 97, 93);
    append_add(96, 96, 93);

    append_and(97, 97, 50);
    append_and(96, 96, 50);

    append_left(97, 97, x*k);
    append_left(96, 96, y*k);

    vector<bool> allButXAndY(b1);
    for(int i = 0; i < b1; i ++){
        allButXAndY[i] = (i/k != x) && (i/k != y);
    }

    append_store(90, allButXAndY);

    append_and(0, 0, 90);

    append_or(0, 0, 97);
    append_or(0, 0, 96);

    return;
}

void construct_instructions(int s, int n, int k, int q) {
	vector<bool> k1(b1);
	for(int i = 0; i < k; i ++){
        k1[i] = 1;
	}
	vector<bool> one(b1);
	vector<bool> zero(b1);
	one[0] = 1;
	append_store(50, k1);
	append_store(ONE, one);

	for(int i = 0; i < n; i ++){
        for(int j = 0; j < n-1; j ++){
            swap1(j, j+1, k);
        }
	}

	return;
}

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