#ifndef Nhoksocqt1
#include "abc.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
#define names ajfhqwurhuqerw
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 702;
const int MAXM = 1003;
map<string, string> Map;
string names[MAXN], letter[MAXM][2];
int ans[MAXN][16], tmp[16], n, m;
int isSend[MAXN][MAXM], isRecei[MAXN][MAXM], ok[MAXN][MAXN];
int alice(const int n, const char str[][5], const unsigned short numbers[], bool outputs_alice[]) {
Map.clear();
vector<string> vString;
for (int i = 0; i < n; ++i) {
names[i].clear();
for (int j = 0; j < 5; ++j) {
if(str[i][j] == '\0')
break;
names[i].push_back(str[i][j]);
}
vString.push_back(names[i]);
}
sort(vString.begin(), vString.end());
vString.erase(unique(vString.begin(), vString.end()), vString.end());
int cnt(0);
for (int it = 0; it < sz(vString); ++it) {
string str(vString[it]);
if(Map.find(str) == Map.end()) {
string tmp;
if(cnt >= 26) {
tmp = "a" + char(cnt % 26 + 'a');
} else {
tmp = char(cnt + 'a');
}
Map[str] = tmp;
str = tmp;
++cnt;
}
}
for (int i = 0; i < n; ++i)
names[i] = Map[names[i]];
int lA(0);
outputs_alice[lA++] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < sz(names[i]); ++j) {
int val = names[i][j] - 'a';
for (int k = 0; k < 16; ++k)
outputs_alice[lA++] = val >> k & 1;
}
}
for (int i = 0; i < n; ++i) {
for (int k = 0; k < 16; ++k)
outputs_alice[lA++] = numbers[i] >> k & 1;
}
return lA;
}
int bob(const int m, const char send[][5], const char recei[][5], bool outputs_bob[]) {
Map.clear();
vector<string> vString;
for (int i = 0; i < m; ++i) {
letter[i][0].clear();
letter[i][1].clear();
for (int j = 0; j < 5; ++j) {
if(send[i][j] == '\0')
break;
letter[i][0].push_back(send[i][j]);
}
for (int j = 0; j < 5; ++j) {
if(recei[i][j] == '\0')
break;
letter[i][1].push_back(recei[i][j]);
}
vString.push_back(letter[i][0]);
vString.push_back(letter[i][1]);
}
sort(vString.begin(), vString.end());
vString.erase(unique(vString.begin(), vString.end()), vString.end());
int cnt(0);
for (int it = 0; it < sz(vString); ++it) {
string str(vString[it]);
if(Map.find(str) == Map.end()) {
string tmp;
if(cnt >= 26) {
tmp = "a" + char(cnt % 26 + 'a');
} else {
tmp = char(cnt + 'a');
}
Map[str] = tmp;
str = tmp;
++cnt;
}
}
for (int i = 0; i < m; ++i) {
letter[i][0] = Map[letter[i][0]];
letter[i][1] = Map[letter[i][1]];
}
int lB(0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < sz(letter[i][0]); ++j) {
int val = letter[i][0][j] - 'a';
for (int k = 0; k < 5; ++k)
outputs_bob[lB++] = val >> k & 1;
}
for (int j = 0; j < sz(letter[i][1]); ++j) {
int val = letter[i][1][j] - 'a';
for (int k = 0; k < 5; ++k)
outputs_bob[lB++] = val >> k & 1;
}
}
return lB;
}
#ifdef Nhoksocqt1
bool alice_output[100 * MAXM], bob_output[100 * MAXM], val[20000 * MAXM];
#endif // Nhoksocqt1
int circuit(const int la, const int lb, int ope[], int gate[][2], int outputs_circuit[][16]) {
int l(la + lb), n = (la - 1) / 16 / 2, m = lb / 2 / 5;
for (int i = 0; i < n; ++i) {
for (int k = 0; k < 5; ++k) {
ope[l] = 5;
gate[l][0] = gate[l][1] = i * 16 + 1 + k;
++l;
}
}
for (int j = 0; j < 16; ++j) {
ope[l] = 8;
gate[l][0] = gate[l][1] = 0;
for (int i = 0; i < n; ++i)
ans[i][j] = l;
++l;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int lst(-1);
for (int k = 0; k < 5; ++k) {
ope[l] = 6;
gate[l][0] = la + lb + i * 5 + k, gate[l][1] = la + j * 10 + k;
++l;
if(lst >= 0) {
ope[l] = 8;
gate[l][0] = lst, gate[l][1] = l - 1;
++l;
}
lst = l - 1;
}
isSend[i][j] = lst;
lst = -1;
for (int k = 0; k < 5; ++k) {
ope[l] = 6;
gate[l][0] = la + lb + i * 5 + k, gate[l][1] = la + j * 10 + 5 + k;
++l;
if(lst >= 0) {
ope[l] = 8;
gate[l][0] = lst, gate[l][1] = l - 1;
++l;
}
lst = l - 1;
}
isRecei[i][j] = lst;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int lst(-1);
for (int k = 0; k < m; ++k) {
ope[l] = 8;
gate[l][0] = isSend[j][k], gate[l][1] = isRecei[i][k];
++l;
if(lst >= 0) {
ope[l] = 14;
gate[l][0] = lst, gate[l][1] = l - 1;
++l;
}
lst = l - 1;
}
ok[i][j] = lst;
for (int k = 0; k < 16; ++k) {
ope[l] = 8;
gate[l][0] = ok[i][j], gate[l][1] = (n + j) * 16 + 1 + k;
tmp[k] = l;
++l;
}
for (int j = 0; j < 16; ++j) {
int newa1[16], newa2[16];
for (int t = 0; t < 16; ++t) {
ope[l] = 6;
gate[l][0] = ans[i][t], gate[l][1] = tmp[t];
newa1[t] = l;
++l;
}
ope[l] = 8;
gate[l][0] = gate[l][1] = 16;
newa2[0] = l;
++l;
for (int t = 1; t < 16; ++t) {
ope[l] = 8;
gate[l][0] = ans[i][t - 1], gate[l][1] = tmp[t - 1];
newa2[t] = l;
++l;
}
for (int j = 0; j < 16; ++j)
ans[i][j] = newa1[j], tmp[j] = newa2[j];
}
for (int j = 0; j < 16; ++j) {
ope[l] = 14;
gate[l][0] = ans[i][j], gate[l][1] = tmp[j];
ans[i][j] = l;
++l;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 16; ++j)
outputs_circuit[i][j] = ans[i][j];
}
return l;
}
#ifdef Nhoksocqt1
int ope[100 * MAXM], gate[100 * MAXM][2], circuit_output[MAXN][16];
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "abc"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
unsigned short numbers[MAXN];
char names[MAXN][5];
char send[MAXM][5], reic[MAXM][5];
int n, m;
cin >> n;
for (int i = 0; i < n; ++i) {
string str;
cin >> str;
for (int j = 0; j < sz(str); ++j)
names[i][j] = str[j];
names[i][sz(str)] = '\0';
cin >> numbers[i];
}
cin >> m;
for (int i = 0; i < m; ++i) {
string sa, sb;
cin >> sa >> sb;
for (int j = 0; j < sz(sa); ++j)
send[i][j] = sa[j];
for (int j = 0; j < sz(sb); ++j)
reic[i][j] = sb[j];
send[i][sz(sa)] = reic[i][sz(sb)] = '\0';
}
int la = alice(n, names, numbers, alice_output);
int lb = bob(m, send, reic, bob_output);
int l = circuit(la, lb, ope, gate, circuit_output);
for (int i = 0; i < la; ++i)
val[i] = alice_output[i];
for (int i = la; i < la + lb; ++i)
val[i] = bob_output[i - la];
cout << "ALICE: " << la << '\n';
for (int it = 0; it < la; ++it)
cout << val[it] << ' '; cout << '\n';
cout << "BOB: " << lb << '\n';
for (int it = 0; it < lb; ++it)
cout << val[la + it] << ' '; cout << '\n';
for (int i = la + lb; i < l; ++i) {
int x(gate[i][0]), y(gate[i][1]);
if(ope[i] == 8) {
val[i] = (val[x] & val[y]);
} else
if(ope[i] == 14) {
val[i] = (val[x] | val[y]);
} else
if(ope[i] == 6) {
val[i] = (val[x] ^ val[y]);
} else
if(ope[i] == 5) {
val[i] = !val[x];
} else {
abort();
}
}
for (int i = 0; i < n; ++i) {
int res(0);
for (int j = 0; j < 16; ++j)
res |= val[circuit_output[i][j]] << j;
cout << res << '\n';
}
cout << "OK:\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cout << val[ok[i][j]] << ' '; cout << '\n';
}
return 0;
}
#endif // Nhoksocqt1
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1988 KB |
WA circuit() returns invalid operand (<0 or >=current label) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1988 KB |
WA circuit() returns invalid operand (<0 or >=current label) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1988 KB |
WA circuit() returns invalid operand (<0 or >=current label) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
16704 KB |
Correct! |
| 2 |
Correct |
57 ms |
36100 KB |
Correct! |
| 3 |
Correct |
71 ms |
43348 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
16704 KB |
Correct! |
| 2 |
Correct |
57 ms |
36100 KB |
Correct! |
| 3 |
Correct |
71 ms |
43348 KB |
Correct! |
| 4 |
Correct |
67 ms |
38768 KB |
Correct! |
| 5 |
Correct |
79 ms |
44408 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
16704 KB |
Correct! |
| 2 |
Correct |
57 ms |
36100 KB |
Correct! |
| 3 |
Correct |
71 ms |
43348 KB |
Correct! |
| 4 |
Correct |
67 ms |
38768 KB |
Correct! |
| 5 |
Correct |
79 ms |
44408 KB |
Correct! |
| 6 |
Incorrect |
24 ms |
1980 KB |
Bob lengths are not all equal. |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
4276 KB |
Bob lengths are not all equal. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
4276 KB |
Bob lengths are not all equal. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1988 KB |
WA circuit() returns invalid operand (<0 or >=current label) |
| 2 |
Halted |
0 ms |
0 KB |
- |
