oj.uz

답안 #768180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768180 2023-06-27T16:29:19 Z green_gold_dog 앨리스, 밥, 서킷 (APIO23_abc) C++17
66 / 100
 435 ms 494880 KB 
#include "abc.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

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

constexpr ll LOG = 16, COLC = 27, ADD = 1, LOG2 = 20, SLOGA = LOG + LOG2, SLOGB = LOG2 * 2;

// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char name[][5],
    /*  in */ const unsigned short num[],
    /* out */ bool oa[]
) {
	ll last = 0;
	for (ll i = 0; i < n; i++) {
		ll now = 0;
		for (auto j : name[i]) {
			if (j < 'a') {
				break;
			}
			now *= COLC;
			now += j - 'a' + ADD;
		}
		for (ll j = 0; j < LOG2; j++) {
			oa[last] = now % 2;
			now /= 2;
			last++;
		}
		now = num[i];
		for (ll j = 0; j < LOG; j++) {
			oa[last] = now % 2;
			now /= 2;
			last++;
		}
	}
	return last;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char s[][5],
    /*  in */ const char r[][5],
    /* out */ bool ob[]
) {
	ll last = 0;
	for (ll i = 0; i < m; i++) {
		ll now = 0;
		for (auto j : s[i]) {
			if (j < 'a') {
				break;
			}
			now *= COLC;
			now += j - 'a' + ADD;
		}
		for (ll j = 0; j < LOG2; j++) {
			ob[last] = now % 2;
			now /= 2;
			last++;
		}
		now = 0;
		for (auto j : r[i]) {
			if (j < 'a') {
				break;
			}
			now *= COLC;
			now += j - 'a' + ADD;
		}
		for (ll j = 0; j < LOG2; j++) {
			ob[last] = now % 2;
			now /= 2;
			last++;
		}
	}
	return last;
}

pair<ll, ll> sum2(ll a, ll b, ll& last, int o[], int op[][2]) {
	o[last] = OP_XOR;
	op[last][0] = a;
	op[last][1] = b;
	last++;
	o[last] = OP_AND;
	op[last][0] = a;
	op[last][1] = b;
	last++;
	return make_pair(last - 2, last - 1);
}

pair<ll, ll> sum3(ll a, ll b, ll c, ll& last, int o[], int op[][2]) {
	auto[f, s] = sum2(a, b, last, o, op);
	auto[f2, s2] = sum2(f, c, last, o, op);
	o[last] = OP_OR;
	op[last][0] = s;
	op[last][1] = s2;
	last++;
	return make_pair(f2, last - 1);
}

vector<ll> sum(vector<ll> s1, vector<ll> s2, ll& last, int o[], int op[][2]) {
	vector<ll> ans;
	auto[f, s] = sum2(s1[0], s2[0], last, o, op);
	ans.push_back(f);
	ll per = s;
	for (ll i = 1; i < LOG; i++) {
		auto[f, s] = sum3(s1[i], s2[i], per, last, o, op);
		ans.push_back(f);
		per = s;
	}
	return ans;
}

ll check(vector<ll> fir, vector<ll> sec, ll& last, int o[], int op[][2]) {
	ll n = fir.size();
	for (ll i = 0; i < n; i++) {
		o[last] = OP_EQUAL;
		op[last][0] = fir[i];
		op[last][1] = sec[i];
		last++;
	}
	ll end = last - 1;
	for (ll i = last - n; i != end; i++) {
		o[last] = OP_AND;
		op[last][0] = i;
		op[last][1] = last - 1;
		last++;
	}
	return last - 1;
}

// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int o[],
    /* out */ int op[][2],
    /* out */ int oc[][16]
) {
	ll n = la / SLOGA;
	ll m = lb / SLOGB;
	if (n == 0) {
		return 0;
	}
	vector<vector<ll>> name(n), num(n), from(m), to(m);
	vector<vector<ll>> nans(n);
	ll last = 0;
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < LOG2; j++) {
			name[i].push_back(last);
			last++;
		}
		for (ll j = 0; j < LOG; j++) {
			num[i].push_back(last);
			last++;
		}
	}
	for (ll i = 0; i < m; i++) {
		for (ll j = 0; j < LOG2; j++) {
			from[i].push_back(last);
			last++;
		}
		for (ll j = 0; j < LOG2; j++) {
			to[i].push_back(last);
			last++;
		}
	}
	ll ZERO = last;
	o[last] = OP_ZERO;
	op[last][0] = 0;
	op[last][1] = 1;
	last++;
	for (ll i = 0; i < m; i++) {
		vector<ll> sall;
		for (ll j = 0; j < n; j++) {
			ll need = check(name[j], from[i], last, o, op);
			vector<ll> nnum;
			for (ll s = 0; s < LOG; s++) {
				nnum.push_back(last);
				o[last] = OP_AND;
				op[last][0] = need;
				op[last][1] = num[j][s];
				last++;
			}
			if (sall.empty()) {
				sall = nnum;
			} else {
				vector<ll> nsall;
				for (ll s = 0; s < LOG; s++) {
					nsall.push_back(last);
					o[last] = OP_OR;
					op[last][0] = sall[s];
					op[last][1] = nnum[s];
					last++;
				}
				sall = nsall;
			}
		}
		for (ll j = 0; j < n; j++) {
			ll need = check(name[j], to[i], last, o, op);
			vector<ll> nnum;
			for (ll s = 0; s < LOG; s++) {
				nnum.push_back(last);
				o[last] = OP_AND;
				op[last][0] = need;
				op[last][1] = sall[s];
				last++;
			}
			if (nans[j].empty()) {
				nans[j] = nnum;
			} else {
				nans[j] = sum(nans[j], nnum, last, o, op);
			}
		}
	}
	for (ll i = 0; i < n; i++) {
		if (nans[i].empty()) {
			nans[i].resize(LOG, ZERO);
		}
		for (ll s = 0; s < LOG; s++) {
			oc[i][s] = nans[i][s];
		}
	}
	return last;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1268 KB Correct!
2 Correct 2 ms 1212 KB Correct!

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1268 KB Correct!
2 Correct 2 ms 1212 KB Correct!
3 Correct 106 ms 20840 KB Correct!
4 Correct 113 ms 20852 KB Correct!

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3248 KB Correct!
2 Correct 102 ms 63536 KB Correct!
3 Correct 132 ms 82064 KB Correct!

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3248 KB Correct!
2 Correct 102 ms 63536 KB Correct!
3 Correct 132 ms 82064 KB Correct!
4 Correct 110 ms 63564 KB Correct!
5 Correct 139 ms 81988 KB Correct!

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3248 KB Correct!
2 Correct 102 ms 63536 KB Correct!
3 Correct 132 ms 82064 KB Correct!
4 Correct 110 ms 63564 KB Correct!
5 Correct 139 ms 81988 KB Correct!
6 Correct 99 ms 59480 KB Correct!
7 Correct 199 ms 123372 KB Correct!

Subtask #7
0.0 / 18.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1268 KB Correct!
2 Correct 2 ms 1212 KB Correct!
3 Correct 106 ms 20840 KB Correct!
4 Correct 113 ms 20852 KB Correct!
5 Correct 7 ms 3248 KB Correct!
6 Correct 102 ms 63536 KB Correct!
7 Correct 132 ms 82064 KB Correct!
8 Correct 110 ms 63564 KB Correct!
9 Correct 139 ms 81988 KB Correct!
10 Correct 99 ms 59480 KB Correct!
11 Correct 199 ms 123372 KB Correct!
12 Runtime error 435 ms 494880 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -