Submission #1190298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190298		kirito	Alice, Bob, and Circuit (APIO23_abc)	C++20	66 / 100	186 ms	239064 KiB

abc

#include "abc.h"

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

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1

const int MAX_LEN = 4;

// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
	int cur = 0;
	for (int i = 0; i < n; i++) {
		bool ended = false;
		for (int j = 0; j < MAX_LEN; j++) {
			if (names[i][j] == 0)
				ended = true;
			int val = 0;
			if (!ended) val = names[i][j] - 'a' + 1;
			for (int k = 0; k < 5; k++) {
				outputs_alice[cur++] = val % 2;
				val /= 2;
			}
		}
		int val = numbers[i];
		for (int k = 0; k < 16; k++) {
			outputs_alice[cur++] = val % 2;
			val /= 2;
		}
	}
    return cur;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
	int cur = 0;
	for (int i = 0; i < m; i++) {
		bool ended = false;
		for (int j = 0; j < MAX_LEN; j++) {
			if (senders[i][j] == 0)
				ended = true;
			int val = 0;
			if (!ended) val = senders[i][j] - 'a' + 1;
			for (int k = 0; k < 5; k++) {
				outputs_bob[cur++] = val % 2;
				val /= 2;
			}
		}
		ended = false;
		for (int j = 0; j < MAX_LEN; j++) {
			if (recipients[i][j] == 0)
				ended = true;
			int val = 0;
			if (!ended) val = recipients[i][j] - 'a' + 1;
			for (int k = 0; k < 5; k++) {
				outputs_bob[cur++] = val % 2;
				val /= 2;
			}
		}
	}
    return cur;
}

void add_op(int op, int x, int y, int &cur, int operations[], int operands[][2]) {
	operations[cur] = op;
	operands[cur][0] = x;
	operands[cur][1] = y;
	cur++;
}

const int SUM_LEN = 74;
int add_summator(int a, int b, int &cur, int op1[], int op2[][2], int bits = 16) {
	int start = cur;
	add_op(OP_AND, a, b, cur, op1, op2);
	for (int i = 1; i + 1 < bits; i++) {
		add_op(OP_XOR, a + i, b + i, cur, op1, op2);
		add_op(OP_AND, cur - 1, cur - 2, cur, op1, op2);
		add_op(OP_AND, a + i, b + i, cur, op1, op2);
		add_op(OP_OR, cur - 1, cur - 2, cur, op1, op2);
	}
	add_op(OP_XOR, a + bits - 1, b + bits - 1, cur, op1, op2);
	int res = cur;
	add_op(OP_XOR, a, b, cur, op1, op2);
	for (int i = 0; i + 1 < bits; i++)
		add_op(OP_XOR, start + i * 4, start + i * 4 + 1, cur, op1, op2);
	return res;
}

// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs_circuit[][16]
) {
	int cur = la + lb;
	int namelen = MAX_LEN * 5;
	int numlen = 16;
	int p1sz = namelen + namelen + numlen;
	int n = la / (namelen + numlen);
	int m = lb / (namelen + namelen);
	vector<int> pos;
	for (int i = 0; i < m; i++) {
		int sti = cur;
		int bbeg = la + i * (namelen + namelen);
		for (int j = 0; j < n; j++) {
			int stj = cur;
			int abeg = j * (namelen + numlen);
			for (int k = 0; k < namelen; k++)
				add_op(OP_EQUAL, abeg + k, bbeg + k, cur, operations, operands);
			add_op(OP_X0, stj + 0, 0, cur, operations, operands);
			for (int k = 1; k < namelen; k++)
				add_op(OP_AND, cur - 1, stj + k, cur, operations, operands);
			int u = cur - 1;
			for (int k = 0; k < numlen; k++)
				add_op(OP_AND, u, abeg + namelen + k, cur, operations, operands);
		}
		int eni = cur;
		for (int k = 0; k < numlen; k++)
			add_op(OP_X0, sti + namelen + namelen + k, 0, cur, operations, operands);
		int u = eni;
		for (int k = sti + p1sz + namelen + namelen; k < eni; k += p1sz)
			u = add_summator(u, k, cur, operations, operands);
		pos.push_back(u);
	}
	vector<int> respos;
	for (int i = 0; i < n; i++) {
		int sti = cur;
		int abeg = i * (namelen + numlen);
		for (int j = 0; j < m; j++) {
			int stj = cur;
			int bbeg = la + j * (namelen + namelen) + namelen;
			for (int k = 0; k < namelen; k++)
				add_op(OP_EQUAL, abeg + k, bbeg + k, cur, operations, operands);
			add_op(OP_X0, stj + 0, 0, cur, operations, operands);
			for (int k = 1; k < namelen; k++)
				add_op(OP_AND, cur - 1, stj + k, cur, operations, operands);
			int u = cur - 1;
			for (int k = 0; k < numlen; k++)
				add_op(OP_AND, u, pos[j] + k, cur, operations, operands);
		}
		int eni = cur;
		int u = eni;
		if (m > 0) {
			for (int k = 0; k < numlen; k++)
				add_op(OP_X0, sti + namelen + namelen + k, 0, cur, operations, operands);
			for (int k = sti + p1sz + namelen + namelen; k < eni; k += p1sz)
				u = add_summator(u, k, cur, operations, operands);
		} else {
			for (int k = 0; k < numlen; k++)
				add_op(OP_ZERO, 0, 0, cur, operations, operands);
		}
		respos.push_back(u);
	}
	for (int i = 0; i < n; i++)
	for (int j = 0; j < 16; j++)
		outputs_circuit[i][j] = respos[i] + j;
    return cur;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24
• Subtask 6: 6 / 6
• Subtask 7: 0 / 18
• Subtask 8: 0 / 10
• Subtask 9: 0 / 6