Submission #623942

# Submission time Handle Problem Language Result Execution time Memory
623942 2022-08-07T03:32:52 Z Temmie Bit Shift Registers (IOI21_registers) C++17
64 / 100
2 ms 596 KB
/*
 * 
 * get a 1 bit on b10 if x <= y and 0 bit otherwise (in reg2)
 * where x is number on bit 0..9 in reg0 and y is number on bit 0..9 in reg1
 * z is 11 bit number in reg2 on bit 0..10
 * make z -> -y - 1 by doing y ^ 0b11111111111 (11 ones)
 * make z -> z + x
 * if bit 11 is on in reg2: x <= y since number is still negative
 * else: x > y
 * 
 * preset:
 * 1 mask 00..0011..1100..0011..11...
 * 2 mask 0x10 1 0x9 0x10 1 ...
 * 3 mask to save value to regS in offset 0
 * 4 mask to save value(s) to regS in offset 1
 * 
 * 1  store potential last value in reg0 into regS with and operator with preset 1bits-mask (if n is odd)
 * 1  take all odd numbers from reg0 and copy them to reg1:
 * 2  use mask 00..0011..1100..0011..11... to get reg1 with only odd indices
 * 3  shift to the left by 10 to align with reg0
 * 5  perform above steps to get x ?<= y bits for each number in parallel
 * 6  filer out all stray bits by using mask with 0x10 1 0x9 0x10 1 ...
 * 7  then shift to the left by 1 and or that on
 * 8  then shift to the left by 2 and or that on
 * 9  then shift to the left by 4 and or that on
 * 10 then shift to the left by 2 and or that on to get 11 ones if b10 was 1 and zeroes otherwise
 * 11 then and the resulting mask with reg1 to get potential values where y >= x
 * 13 then perform not operator on the mask and perform and operator on reg0 to get values where x > y
 * 15 then shift to the right by 10 and or the result to regT to insert the elements
 * 17 then set regU to reg0 xor reg1 xor reg2 to get a register with the values with the lesser values
 * 18 insert regU into regT with or and move result to reg0
 * 19 or in the stored value in regS
 * 
 * repeat above step but starting with index 1
 * store value 0 (always) and potential last value (if n is even) like step 1 in above sequence
 * 
 * repeat n times where offset (0 or 1) is alternated between (about half each)
 * 
*/

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

int s, n, k, q;
int alter = 99;
int bkp1 = 98;
int regS0 = 97;
int regS1 = 96;
int nregS0 = 95;
int nregS1 = 94;
int regStore = 93;
int kp1ones = 92;
int nalter = 91;

// 7 queries
void prepare_masks() {
	std::vector <bool> mask(2000, 0);
	for (int i = 1; i < n; i += 2) {
		int start = i * k;
		for (int j = 0; j < k; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(alter, mask);
	mask.assign(2000, 0);
	for (int i = 0; i < n; i += 2) {
		int start = i * k + k;
		mask[start] = 1;
	}
	append_store(bkp1, mask);
	mask.assign(2000, 0);
	if (n & 1) {
		int start = (n - 1) * k;
		for (int j = 0; j < k; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(regS0, mask);
	mask.assign(2000, 0);
	for (int j = 0; j < k; j++) {
		mask[j] = 1;
	}
	if (~n & 1) {
		int start = (n - 1) * k;
		for (int j = 0; j < k; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(regS1, mask);
	append_not(nregS0, regS0);
	append_not(nregS1, regS1);
	mask.assign(2000, 0);
	for (int i = 0; i < n; i += 2) {
		int start = i * k;
		for (int j = 0; j < k + 1; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(kp1ones, mask);
	append_not(nalter, alter);
}

// 3 queries
void compare_even_pos() {
	append_xor(2, kp1ones, 1);
	append_add(2, 2, 0);
	append_and(2, 2, bkp1);
}

// 22 queries worst case
void go0() {
	append_and(regStore, 0, regS0);
	append_and(0, 0, nregS0);
	append_and(1, 0, alter);
	append_right(1, 1, k);
	append_and(0, nalter, 0);
	compare_even_pos();
	append_right(2, 2, 1);
	int left = k - 1;
	int sofar = 1;
	while (left) {
		if (sofar <= left) {
			append_right(3, 2, sofar);
			append_or(2, 2, 3);
			left -= sofar;
			sofar <<= 1;
		} else {
			append_right(3, 2, left);
			append_or(2, 2, 3);
			break;
		}
	}
	append_and(3, 2, 1);
	append_not(2, 2);
	append_and(4, 2, 0);
	append_or(3, 3, 4);
	// now register 3 has value of greater number between the two compared values
	append_xor(4, 3, 0);
	append_xor(4, 4, 1);
	// now register 4 has value of lesser number betweren the two compared values
	append_left(3, 3, k);
	append_or(0, 4, 3);
	// now register 0 has result of bubbel sort step
	append_or(0, 0, regStore);
	// now register 0 has stray value too
}

// 22 queries worst case
void go1() {
	append_and(regStore, 0, regS1);
	append_and(0, 0, nregS1);
	append_and(1, 0, alter);
	append_left(1, 1, k);
	append_and(0, nalter, 0);
	compare_even_pos();
	append_right(2, 2, 1);
	int left = k - 1;
	int sofar = 1;
	while (left) {
		if (sofar <= left) {
			append_right(3, 2, sofar);
			append_or(2, 2, 3);
			left -= sofar;
			sofar <<= 1;
		} else {
			append_right(3, 2, left);
			append_or(2, 2, 3);
			break;
		}
	}
	append_and(3, 2, 1);
	append_not(2, 2);
	append_and(4, 2, 0);
	append_or(3, 3, 4);
	// now register 3 has value of greater number between the two compared values
	append_xor(4, 3, 0);
	append_xor(4, 4, 1);
	// now register 4 has value of lesser number betweren the two compared values
	append_right(4, 4, k);
	append_or(0, 4, 3);
	// now register 0 has result of bubbel sort step
	append_or(0, 0, regStore);
	// now register 0 has stray value too
}

// 7 + n * 22 queries worst case (n = 100, k = 10 -> 2207)
void construct_instructions(int _s, int _n, int _k, int _q) {
	s = _s, n = _n, k = _k, q = _q;
	prepare_masks();
	for (int i = 0; i < n; i++) {
		if (i & 1) {
			go1();
		} else {
			go0();
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct