| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 756914 | doowey | Sequence (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
// 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
struct state{
string num;
int numb;
int idx;
bool operator< (const state &si) const {
return num < si.num;
}
};
int alice(const int n, const char names[][5],const unsigned short numbers[],bool outputs_alice[]) {
vector<state> nums;
for(int i = 0 ; i < n; i ++ ){
nums.push_back({names[i], numbers[i], i});
}
sort(nums.begin(), nums.end());
int len = 0;
for(int i = 0 ; i < n; i ++ ){
for(int j = 0 ; j < 16; j ++ ){
if((nums[i].numb & (1 << j))){
outputs_alice[len] = 1;
}
else{
outputs_alice[len] = 0;
}
len ++ ;
}
}
int bi;
for(int i = 0 ; i < n; i ++ ){
bi = 0;
for(int j = 0 ; j + 1 < n; j ++ ){
if(nums[j].idx > nums[j + 1].idx){
bi = 1;
swap(nums[j], nums[j + 1]);
}
else{
bi = 0;
}
outputs_alice[len] = bi;
len ++ ;
}
}
return len;
}
// Bob
int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]) {
vector<string> pp;
for(int i = 0 ; i < m ; i ++ ){
pp.push_back(senders[i]);
pp.push_back(recipients[i]);
}
sort(pp.begin(), pp.end());
pp.resize(unique(pp.begin(), pp.end()) - pp.begin());
int n = pp.size();
vector<vector<bool>> E(n);
for(int i = 0 ; i < n ; i ++ ){
E[i].resize(n);
}
int iu, iv;
for(int i = 0 ; i < m ; i ++ ){
string u = senders[i];
string v = recipients[i];
iu = lower_bound(pp.begin(), pp.end(), u) - pp.begin();
iv = lower_bound(pp.begin(), pp.end(), v) - pp.begin();
E[iu][iv] = true;
}
int idx = 0;
for(int j = 0; j < n; j ++) {
for(int i = 0 ; i < n ; i ++ ){
outputs_bob[idx] = E[i][j];
idx ++ ;
}
}
return idx;
}
int circuit(const int la, const int lb, int operations[],int operands[][2], int outputs_circuit[][16]) {
int st = la + lb;
int n = 1;
while(n * (n - 1) + 16 * n != la) n ++ ;
int add;
int edge = la;
vector<vector<int>> E(n);
vector<vector<int>> bubble(n);
int bub = 16 * n;
for(int i = 0 ; i < n; i ++ ){
E[i].resize(n);
bubble[i].resize(n);
for(int j = 0 ; j + 1 < n; j ++ ){
bubble[i][j] = bub;
bub ++ ;
}
}
for(int j = 0 ; j < n; j ++ ){
for(int i = 0 ; i < n; i ++ ){
E[i][j]=edge;
edge++;
}
}
int place;
int n_add;
for(int j = 0; j < n; j ++ ){
vector<int> ind;
for(int bit = 0; bit < 16; bit ++ ){
place = st;
st ++ ;
operations[place] = 0;
operands[place][0] = operands[place][1] = 0;
ind.push_back(place);
}
for(int bit = 0; bit < 16; bit ++ ){ // do all additions FROM i-th person WITH bit-th bit
for(int i = 0 ; i < n ; i ++ ){
add = st;
st ++ ;
operations[add] = 8;
operands[add][0] = E[i][j];
operands[add][1] = i * 16 + bit;
vector<int> nw = ind;
for(int g = bit; g < 16; g ++ ){
place = st;
st ++ ;
operations[place] = 6;
operands[place][0] = ind[g];
operands[place][1] = add;
nw[g] = place;
n_add = st;
st ++ ;
operations[n_add] = 8;
operands[n_add][0] = ind[g];
operands[n_add][1] = add;
add = n_add;
}
ind = nw;
}
}
for(int b = 0; b < 16; b ++ ){
outputs_circuit[j][b]=ind[b];
}
}
int fW;
int C;
/*
for(int i = 0 ; i < n; i ++ ){
for(int j = 0 ; j + 1 < n; j ++ ){
for(int b = 0; b < 16; b ++ ){
int W = st;
st ++ ;
operations[W] = 6;
operands[W][0] = outputs_circuit[j][b];
operands[W][1] = outputs_circuit[j + 1][b];
fW = st;
st ++ ;
operations[fW] = 8;
operands[fW][0] = W;
operands[fW][1] = bubble[i][j];
C = st;
st ++ ;
operations[C] = 6;
operands[C][0] = outputs_circuit[j][b];
operands[C][1] = fW;
outputs_circuit[j][b] = C;
C = st;
st ++ ;
operations[C] = 6;
operands[C][0] = outputs_circuit[j + 1][b];
operands[C][1] = fW;
outputs_circuit[j + 1][b] = C;
}
}
}
*/
return st;
}