oj.uz

답안 #749642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749642 2023-05-28T10:38:51 Z happypotato 앨리스, 밥, 서킷 (APIO23_abc) C++17
66 / 100
 87 ms 10192 KB 
#include "abc.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define ld long double

// 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


// Alice
int // returns la
alice(
	/*  in */ const int n,
	/*  in */ const char names[][5],
	/*  in */ const unsigned short numbers[],
	/* out */ bool outputs_alice[]
) {
	// Type A subtasks
	if (n == 1) {
		for (int i = 0; i < 16; i++) {
			outputs_alice[i] = bool(numbers[0] & (1 << i));
		}
		return 16;
	}
	// Type B subtasks (??)
	if (n <= 30) {
		vector<pair<string, pii>> v;
		for (int i = 0; i < n; i++) {
			string cur = "";
			for (int j = 0; j < 5; j++) cur += names[i][j];
			v.pb({cur, {i, numbers[i]}});
		}
		sort(v.begin(), v.end());
		int ROLL = 0;
		// first n * 16: store values
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 16; j++) {
				outputs_alice[ROLL] = (i >= n ? 0 : bool(v[i].ss.ss & (1 << j)));
				ROLL++;
			}
		}
		// next n * n: store order
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				outputs_alice[ROLL] = (j == v[i].ss.ff);
				// cout << outputs_alice[ROLL];
				ROLL++;
			}
			// cout << endl;
		}
		return ROLL;
	}
	// Type 3 subtasks
	if (n == 676) {
		int ROLL = 0;
		for (int i = 0; i < 676; i++) {
			for (int j = 0; j < 16; j++) {
				outputs_alice[ROLL] = bool(numbers[i] & (1 << j));
				ROLL++;
			}
		}
		return ROLL;
	}
}


// Bob
int // returns lb
bob(
	/*  in */ const int m,
	/*  in */ const char senders[][5],
	/*  in */ const char recipients[][5],
	/* out */ bool outputs_bob[]
) {
	// Type A subtasks
	bool typeA = true;
	char oneuser[5];
	for (int i = 0; i < 5; i++) oneuser[i] = senders[0][i];
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 5; j++) {
			typeA &= (senders[i][j] == oneuser[j]);
			typeA &= (recipients[i][j] == oneuser[j]);
		}
	}
	if (typeA) {
		for (int i = 0; i < 16; i++) {
			outputs_bob[i] = bool(m & (1 << i));
		}
		return 16;
	}

	// Type B subtasks
	if (true) {
		// get all the strings
		set<string> s;
		for (int i = 0; i < m; i++) {
			string cur;
			cur = "";
			for (int j = 0; j < 5; j++) cur += senders[i][j];
			s.insert(cur);
			cur = "";
			for (int j = 0; j < 5; j++) cur += recipients[i][j];
			s.insert(cur);
		}
		int n = s.size();
		map<string, int> conv;
		int ptr = 0;
		for (string cur : s) {
			conv[cur] = ptr++;
		}
		// find if letter exist
		bool exist[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				exist[i][j] = false;
			}
		}
		for (int i = 0; i < m; i++) {
			string cur1 = "", cur2 = "";
			for (int j = 0; j < 5; j++) cur1 += senders[i][j];
			for (int j = 0; j < 5; j++) cur2 += recipients[i][j];
			exist[conv[cur1]][conv[cur2]] = true;
		}
		int ROLL = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				outputs_bob[ROLL] = exist[i][j];
				ROLL++;
			}
		}
		return ROLL;
	}
}

// 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]
) {
	// Useful functions
	int ROLL = la + lb;

	function<int(int, int)> Add = [&](int x, int y) -> int {
		// adds [x, x+16), [y, y+16) to [res, res+16)
		int prev = ROLL;
		// find AND
		for (int i = 0; i < 16; i++) {
			operations[ROLL] = OP_AND;
			operands[ROLL][0] = x + i;
			operands[ROLL][1] = y + i;
			ROLL++;
		}
		// find OR
		for (int i = 0; i < 16; i++) {
			operations[ROLL] = OP_OR;
			operands[ROLL][0] = x + i;
			operands[ROLL][1] = y + i;
			ROLL++;
		}
		// find XOR
		for (int i = 0; i < 16; i++) {
			operations[ROLL] = OP_XOR;
			operands[ROLL][0] = x + i;
			operands[ROLL][1] = y + i;
			ROLL++;
		}
		// 0th bit
		operations[ROLL] = OP_X0;
		operands[ROLL][0] = operands[ROLL][1] = prev + 32;
		ROLL++;
		operations[ROLL] = OP_X0;
		operands[ROLL][0] = operands[ROLL][1] = prev;
		ROLL++;
		operations[ROLL] = OP_X0;
		operands[ROLL][0] = operands[ROLL][1] = prev;
		ROLL++;
		for (int i = 1; i < 16; i++) {
			operations[ROLL] = OP_XOR;
			operands[ROLL][0] = ROLL - 1;
			operands[ROLL][1] = prev + 32 + i;
			ROLL++;
			operations[ROLL] = OP_AND;
			operands[ROLL][0] = ROLL - 2;
			operands[ROLL][1] = prev + 16 + i;
			ROLL++;
			operations[ROLL] = OP_OR;
			operands[ROLL][0] = ROLL - 1;
			operands[ROLL][1] = prev + i;
			ROLL++;
		}
		int res = ROLL;
		for (int i = prev + 48; i < prev + 48 + 48; i += 3) {
			operations[ROLL] = OP_X0;
			operands[ROLL][0] = operands[ROLL][1] = i;
			ROLL++;
		}
		return res;
	};

	function<int(int)> Expand = [&](int x) -> int {
		// 0 if [x, x+16) = 0 and 1 otherwise
		operations[ROLL] = OP_OR;
		operands[ROLL][0] = x; operands[ROLL][1] = x + 1;
		ROLL++;
		for (int i = 2; i < 16; i++) {
			operations[ROLL] = OP_OR;
			operands[ROLL][0] = ROLL - 1; operands[ROLL][1] = x + i;
			ROLL++;
		}
		return ROLL - 1;
	};

	// Type A subtasks
	if (la == 16 && lb == 16) {
		// answer board
		for (int i = 0; i < 16; i++) {
			operations[ROLL] = OP_ZERO;
			operands[ROLL][0] = operands[ROLL][1] = 0;
			ROLL++;
		}
		// -1 board
		for (int i = 0; i < 16; i++) {
			operations[ROLL] = OP_ONE;
			operands[ROLL][0] = operands[ROLL][1] = 0;
			ROLL++;
		}

		int prev = 32;
		int prevboard = 16;
		int allhv = ROLL;
		operations[ROLL] = OP_ONE;
		operands[ROLL][0] = operands[ROLL][1] = 0;
		ROLL++;
		for (int tries = 0; tries < 1024; tries++) {
			int curhv = Expand(prevboard);
			operations[ROLL] = OP_AND;
			operands[ROLL][0] = allhv; operands[ROLL][1] = curhv;
			allhv = ROLL; ROLL++;

			int curadd = ROLL;
			for (int i = 0; i < 16; i++) {
				operations[ROLL] = OP_AND;
				operands[ROLL][0] = i;
				operands[ROLL][1] = allhv;
				ROLL++;
			}

			int address = Add(prev, curadd);
			prev = address;

			// if (tries == 0) {
			// 	for (int i = 0; i < 16; i++) {
			// 		outputs_circuit[0][i] = allhv;
			// 	}
			// 	return ROLL;
			// }

			prevboard = Add(prevboard, 48);
		}
		for (int i = 0; i < 16; i++) {
			outputs_circuit[0][i] = prev + i;
		}
		return ROLL;
	}

	// Type 2 subtasks
	if (true) {
		int n = sqrt(lb);

		int ptrs[n];
		for (int i = 0; i < n; i++) {
			ptrs[i] = ROLL;
			for (int j = 0; j < 16; j++) {
				operations[ROLL] = OP_ZERO;
				operands[ROLL][0] = operands[ROLL][1] = 0;
				ROLL++;
			}
		}
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				// x give letter to y, copy x and add y
				int take = la + x * n + y;
				int copied = ROLL;
				for (int i = 0; i < 16; i++) {
					operations[ROLL] = OP_AND;
					operands[ROLL][0] = take;
					operands[ROLL][1] = x * 16 + i;
					ROLL++;
				}

				ptrs[y] = Add(ptrs[y], copied);
				// for (int i = 0; i < 16; i++) {
				// 	outputs_circuit[x * n + y][i] = ptrs[y] + i;
				// }
			}
		}
		// sort in order later
		int finptrs[n];
		for (int x = 0; x < n; x++) {
			finptrs[x] = ROLL;
			for (int i = 0; i < 16; i++) {
				operations[ROLL] = OP_ZERO;
				operands[ROLL][0] = operands[ROLL][1] = 0;
				ROLL++;
			}
			for (int y = 0; y < n; y++) {
				int cur = ROLL;
				for (int i = 0; i < 16; i++) {
					operations[ROLL] = OP_AND;
					operands[ROLL][0] = ptrs[y] + i;
					operands[ROLL][1] = n * 16 + y * n + x;
					ROLL++;
				}
				finptrs[x] = Add(finptrs[x], cur);
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 16; j++) {
				outputs_circuit[i][j] = finptrs[i] + j;
			}
		}
		return ROLL;
	}
}

Compilation message

abc.cpp: In function 'int alice(int, const char (*)[5], const short unsigned int*, bool*)':
abc.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
   85 | }
      | ^

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6320 KB Correct!

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6320 KB Correct!
2 Correct 9 ms 6264 KB Correct!

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6320 KB Correct!
2 Correct 9 ms 6264 KB Correct!
3 Correct 56 ms 9992 KB Correct!
4 Correct 52 ms 10072 KB Correct!

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 5464 KB Correct!
2 Correct 51 ms 7264 KB Correct!
3 Correct 54 ms 7924 KB Correct!

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 5464 KB Correct!
2 Correct 51 ms 7264 KB Correct!
3 Correct 54 ms 7924 KB Correct!
4 Correct 54 ms 7292 KB Correct!
5 Correct 66 ms 8012 KB Correct!

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 5464 KB Correct!
2 Correct 51 ms 7264 KB Correct!
3 Correct 54 ms 7924 KB Correct!
4 Correct 54 ms 7292 KB Correct!
5 Correct 66 ms 8012 KB Correct!
6 Correct 54 ms 7900 KB Correct!
7 Correct 87 ms 10192 KB Correct!

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 4816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 4816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6320 KB Correct!
2 Correct 9 ms 6264 KB Correct!
3 Correct 56 ms 9992 KB Correct!
4 Correct 52 ms 10072 KB Correct!
5 Correct 13 ms 5464 KB Correct!
6 Correct 51 ms 7264 KB Correct!
7 Correct 54 ms 7924 KB Correct!
8 Correct 54 ms 7292 KB Correct!
9 Correct 66 ms 8012 KB Correct!
10 Correct 54 ms 7900 KB Correct!
11 Correct 87 ms 10192 KB Correct!
12 Runtime error 40 ms 4816 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -