Submission #930047

#	Time	Username	Problem	Language	Result	Execution time	Memory
930047		chrislaiisme	Alice, Bob, and Circuit (APIO23_abc)	C++17	12 / 100	10055 ms	323712 KiB

abc

#include "abc.h"
// #define DEBUG
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<fstream>
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 NUM_LEN = 16, NAME_LEN = 21, OBJ_LEN = 58;
vector<int> deb;
#define FOR_NUM(i) for(int i=0; i<NUM_LEN; i++)
#define FOR_NAME(i) for(int i=0; i<NAME_LEN; i++)
#define all(vec) vec.begin(), vec.end()
#define pii pair<int, int>
#define F first
#define S second
#define mkp make_pair

fstream nothing;
#ifdef DEBUG
#define debug cout
#else
#define debug nothing
#endif

struct stc {
  int X, Y, W;
  stc(int x=0, int y=0, int w=0): X(x), Y(y), W(w) {}
};

void Perm(vector<int> &vec, int l, int r, string &str) {
  if(l >= r) return;
  // ===== Init =====
  int n = r-l+1, len = (n+1)/2;
  int arr[len]; fill(arr, arr+len, 0);

  // ===== Change 1 =====
  vector<bool> change(len, 0);
  while(1) {
    int a = -1, b = -1;
    for(int i=l; i<l+len; i++) {
      for(int j=i+1; j<l+len; j++) {
        if(vec[i]%len == vec[j]%len) {
          a = i, b = j;
          break;
        }
      }
      if(a != -1) break;
    }
    if(a == -1)  break;
    while(1) {
      int c = -1;
      for(int i=l; i<l+len; i++) {
        if(i != b && vec[i]%len == vec[b+len]%len) {
          c = i;
          break;
        }
      }
      change[b-l] = !change[b-l];
      swap(vec[b], vec[b+len]);
      if(c == -1) break;
      a = b, b = c;
    }
  }
  for(int i=0; i<len; i++) str += (char)('0'+change[i]);

  // ===== Recursion =====
  int mp[len];
  for(int i=l; i<l+len; i++) {
    int num = vec[i]%len;
    mp[num] = vec[i];
    vec[i] = num;
  }
  Perm(vec, l, l+len-1, str);
  for(int i=l; i<l+len; i++) vec[i] = mp[vec[i]];
  for(int i=l+len; i<=r; i++) {
    int num = vec[i]%len;
    mp[num] = vec[i];
    vec[i] = num;
  }
  Perm(vec, l+len, r, str);
  for(int i=l+len; i<=r; i++) vec[i] = mp[vec[i]];

  // ===== Change 2 =====
  for(int i=l; i<l+len; i++) {
    if(i+len > r) {
      str += '0';
      continue;
    }
    if(vec[i] > vec[i+len]) {
      str += '1';
      swap(vec[i], vec[i+len]);
    }
    else str += '0';
  }
}

// Alice
int // returns la
alice(
  /*  in */ const int n,
  /*  in */ const char names[][5],
  /*  in */ const unsigned short numbers[],
  /* out */ bool outputs_alice[]
) {

  // =============== Convert to Object ===============
  vector<stc> vec(n);
  for(int i=0; i<n; i++) {
    int name=0, num=numbers[i];
    string str = names[i];
    while(str.length() != 4) str += (char)('a'-1);
    for(auto &j : str) name = name*27+(j-'a'+1);
    vec[i] = stc(name, name, num);
  }

  // =============== Get Pemutation of Ydown -> Init ===============
  vector<int> sorted(n), perm(n);
  for(int i=0; i<n; i++) sorted[i] = vec[i].Y;
  sort(all(sorted), greater<int>());
  map<int, int> mp;
  for(int i=0; i<n; i++) mp[vec[i].Y] = i;
  for(int i=0; i<n; i++) perm[i] = mp[sorted[i]];
  string Ydown_Init = "";
  // for(int i=0; i<n; i++) debug << perm[i] << ' ';
  // debug << endl;
  Perm(perm, 0, n-1, Ydown_Init);
  // debug << Ydown_Init << endl;

  // =============== Sort vec and Pass Data to Circuit (Xup + Ydown_Init) ===============
  sort(vec.begin(), vec.end(), [&](stc a, stc b) {return a.X < b.X;});
  int cur=0;
  for(int i=0; i<n; i++) {
    outputs_alice[cur++] = 0;
    for(int j=0; j<NAME_LEN-1; j++)
      outputs_alice[cur++] = (vec[i].X >> j) & 1;
    outputs_alice[cur++] = 1;
    for(int j=0; j<NAME_LEN-1; j++)
      outputs_alice[cur++] = (vec[i].Y >> j) & 1;
    FOR_NUM(j)
      outputs_alice[cur++] = (vec[i].W >> j) & 1;
  }
  for(int i=0; i<(int)Ydown_Init.length(); i++) outputs_alice[cur++] = Ydown_Init[i] - '0';
  while(cur != 69*n) outputs_alice[cur++] = 0;
  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[]
) {

  // =============== Convert to Object ===============
  vector<stc> vec(m);
  for(int i=0; i<m; i++) {
    int s=0, r=0;
    string S = senders[i], R = recipients[i];
    while(S.length() != 4) S += (char)('a'-1);
    while(R.length() != 4) R += (char)('a'-1);
    for(auto &j : S) s = s*27+(j-'a'+1);
    for(auto &j : R) r = r*27+(j-'a'+1);
    vec[i] = stc(s, r, 0);
  }

  // =============== Get Pemutation of Xdown -> Yup ===============
  vector<pii> sortX(m), sortY(m);
  vector<int> perm(m);
  for(int i=0; i<m; i++) sortX[i] = mkp(vec[i].X, vec[i].Y);
  sortY = sortX;
  sort(all(sortX), [&](pii a, pii b) {if(a.F != b.F) return a.F > b.F; return a.S > b.S;});
  sort(all(sortY), [&](pii a, pii b) {if(a.S != b.S) return a.S < b.S; return a.F < b.F;});
  map<pii, vector<int> > mp;
  for(int i=0; i<m; i++) mp[sortY[i]].push_back(i);
  for(auto &i : mp) i.S.push_back(0);
  for(int i=0; i<m; i++) perm[i] = mp[sortX[i]][mp[sortX[i]].back()++];
  // for(int i=0; i<m; i++) debug << perm[i] << ' ';
  // debug << endl;
  string Xdown_Yup = "";
  Perm(perm, 0, m-1, Xdown_Yup);

  /*
  for(int i=0; i<m; i++) debug << sortX[i].F << ' ';
  debug << endl;
  for(int i=0; i<m; i++) debug << sortX[i].S << ' ';
  debug << endl << endl;
  for(int i=0; i<m; i++) debug << sortY[i].F << ' ';
  debug << endl;
  for(int i=0; i<m; i++) debug << sortY[i].S << ' ';
  debug << endl << endl;
  */
  // debug << Xdown_Yup << endl;

  // =============== Pass Data to Circuit (Xdown + Xdown_Yup) ===============
  int cur=0;
  for(int i=0; i<m; i++) {
    outputs_bob[cur++] = 1;
    for(int j=0; j<NAME_LEN-1; j++)
      outputs_bob[cur++] = (sortX[i].F >> j) & 1;
    outputs_bob[cur++] = 0;
    for(int j=0; j<NAME_LEN-1; j++)
      outputs_bob[cur++] = (sortX[i].S >> j) & 1;
    FOR_NUM(j)
      outputs_bob[cur++] = 0;
  }
  // debug << Xdown_Yup.length() << " ??? " << endl;
  for(int i=0; i<(int)Xdown_Yup.length(); i++) outputs_bob[cur++] = Xdown_Yup[i] - '0';
  while(cur != 69*m) outputs_bob[cur++] = 0;
  return cur;
}

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

  // =============== Initialization ===============
  auto op = [&](int o, int a, int b) {
    operations[cur] = o;
    operands[cur][0] = a, operands[cur][1] = b;
    return cur ++ ;
  };

  int zero = op(OP_ZERO, 0, 0);
  int ZERO = cur;
  FOR_NUM(i) op(OP_ZERO, 0, 0);

  auto ADD = [&](int a, int b) {
    vector<int> carry = {zero}, digit;
    FOR_NUM(i) {
      int d = op(OP_XOR, a+i, b+i);
      int c1 = op(OP_AND, a+i, b+i);
      int c2 = op(OP_AND, d, carry[i]);
      if(i != NUM_LEN-1) carry.push_back(op(OP_OR, c1, c2));
      digit.push_back(d);
    }
    int ret = cur;
    FOR_NUM(i) op(OP_XOR, digit[i], carry[i]);
    return ret;
  };

  // ================ Solve ===============
  int n = la/69, m = lb/69;
  // debug << n << ' ' << m << " ???" << endl;
  if(m == 0) {
    for(int i=0; i<n; i++) {
      int ans = ZERO;
      FOR_NUM(j) outputs_circuit[i][j] = ans + j;
    }
    return cur;
  }

  vector<vector<int> > arr(3, vector<int>(n+m)); // 0 = X, 1 = Y, 2 = W;
  for(int i=0; i<n; i++) {
    arr[0][i] = OBJ_LEN*i;
    arr[1][i] = arr[0][i] + NAME_LEN;
    arr[2][i] = arr[1][i] + NAME_LEN;
  }
  for(int i=0; i<m; i++) {
    arr[0][n+i] = la+OBJ_LEN*i;
    arr[1][n+i] = arr[0][n+i] + NAME_LEN;
    arr[2][n+i] = arr[1][n+i] + NAME_LEN;
  }

  // ===== Add Numbers to Letters =====
  vector<int> signals;

  auto swap = [&](int a, int b, int s) {
    // debug << a << ' ' << b << " ???" << endl;
    vector<int> veca[3], vecb[3];
    for(int j=0; j<3; j++) {
      int len = (j == 2 ? NUM_LEN : NAME_LEN);
      for(int i=0; i<len; i++) {
        int p = arr[j][a]+i, q = arr[j][b]+i;
        // debug << q << ' ' << b << " ??????" << endl;
        int ns = op(OP_NOT_X0, s, 0);
        veca[j].push_back(op(OP_OR, op(OP_AND, p, ns), op(OP_AND, q, s)));
        int num = veca[j].back();
        vecb[j].push_back(op(OP_XOR, op(OP_XOR, num, p), q));
      }
    }
    for(int i=0; i<3; i++) {
      int aa = cur; for(auto &j : veca[i]) op(OP_OR, j, 0);
      int bb = cur; for(auto &j : vecb[i]) op(OP_OR, j, 0);
      arr[i][a] = aa;
      arr[i][b] = bb;
    }
    // debug << a << ' ' << b << " !!!" << endl;
  };

  auto cmp = [&](int a, int b, int k) {
    int s = zero;
    FOR_NAME(i) {
      int p = arr[k][a]+i, q = arr[k][b]+i;
      int eq = op(OP_EQUAL, p, q), num = op(OP_AND, p, op(OP_NOT_X0, q, q));
      s = op(OP_OR, op(OP_AND, s, eq), num);
    }
    signals.push_back(s);
    swap(a, b, s);
  };

  auto merge = [&](auto merge1, int l, int r, int k) {
    // if(l != 0 || r != n+m-1) return;
    if(l >= r) return;
    int m = (l+r)>>1, len = m-l+1;
    for(int i=l; i<=m; i++) {
      if(i+len <= r) cmp(i, i+len, k);
      else signals.push_back(0);
    }
    merge1(merge1, l, m, k); merge1(merge1, m+1, r, k);
  };

  merge(merge, 0, n+m-1, 0);

  /**/ debug << "AAAAA" << endl;

  int num = ZERO;
  for(int i=0; i<n+m; i++) {
    int tmp = cur;
    FOR_NUM(j) op(OP_AND, num+j, arr[0][i]);
    int pos = cur;
    FOR_NUM(j) op(OP_OR, tmp+j, arr[2][i]+j);
    arr[2][i] = pos;
    num = arr[2][i];
  }
  
  /**/ debug << "Add Numbers to Letters Complete" << endl;

  // ===== Unmerge =====
  for(auto &i : signals) debug << i << ' ';
  debug << endl;
  reverse(all(signals));
  int p=0;
  auto unmerge = [&](auto unmerge1, int l, int r) {
    if(l >= r) return;
    int m = (l+r)>>1, len = m-l+1;
    unmerge1(unmerge1, m+1, r); unmerge1(unmerge1, l, m);
    for(int i=m; i>=l; i--) {
      // debug << i << ' ' << i+len << ' ' << signals[p] << " ???" << endl;
      if(i+len <= r) swap(i, i+len, signals[p]);
      p++;
    }
  };
  unmerge(unmerge, 0, n+m-1);

  /**/ debug << "Unmerge Complete" << endl;

  // ===== Change Permutation =====
  int perm = la + OBJ_LEN*m;
  p=0;
  auto calc = [&](auto calc1, int l, int r) {
    if(l >= r) return;
    int n = r-l+1, len = (n+1)/2;
    for(int i=l+len-1; i>=l; i--) p++;
    calc1(calc1, l+len, r);
    calc1(calc1, l, l+len-1);
    for(int i=l+len-1; i>=l; i--) p++;
  };
  auto applyperm = [&](auto applyperm1, int l, int r) {
    if(l >= r) return;
    int num = r-l+1, len = (num+1)/2;

    // ===== Change 2 =====
    for(int i=l+len-1; i>=l; i--) {
      if(i+len <= r)
        swap(i, i+len, perm+p);
      p--;
    }

    // ===== Recursion =====
    applyperm1(applyperm1, l+len, r);
    applyperm1(applyperm1, l, l+len-1);

    // ===== Change 1 =====
    for(int i=l+len-1; i>=l; i--) {
      if(i+len <= r)
        swap(i, i+len, perm+p);
      p--;
    }
  };
  calc(calc, n, n+m-1); p -- ;
  applyperm(applyperm, n, n+m-1);
  auto arr2 = arr;
  for(int i=0; i<m; i++)
    for(int j=0; j<3; j++)
      arr[j][i] = arr2[j][n+i];
  for(int i=0; i<n; i++)
    for(int j=0; j<3; j++)
      arr[j][m+i] = arr2[j][n-1-i];
  /*
  for(int i=0; i<n+m; i++) {
    deb.push_back(arr[0][i]);
    deb.push_back(arr[1][i]);
    deb.push_back(arr[2][i]);
  }
  */

  /**/ debug << "Change Permutation Complete" << endl;

  // ===== Add Number to Person =====
  signals.clear();
  merge(merge, 0, n+m-1, 1);
  num = ZERO;
  for(int i=0; i<n+m; i++) {
    int t = arr[1][i], nt = op(OP_NOT_X0, t, 0);
    // debug << t << ' ' << nt << " ???" << endl;
    int reset = cur;
    FOR_NUM(j) op(OP_AND, arr[2][i]+j, nt);
    arr[2][i] = reset;
    int num2 = cur;
    FOR_NUM(j) op(OP_AND, num+j, t);
    arr[2][i] = ADD(arr[2][i], num2);
    int tmp = cur;
    FOR_NUM(j) op(OP_AND, arr[2][i]+j, nt);
    num = ADD(num, tmp);
    int num3 = cur;
    FOR_NUM(j) op(OP_AND, num+j, nt);
    num = num3;
  }

  /**/ debug << "Add Number to Person Complete" << endl;

  // ===== Unmerge =====
  reverse(all(signals));
  p=0;
  unmerge(unmerge, 0, n+m-1);
  /*
  for(int i=0; i<n+m; i++) {
    deb.push_back(arr[0][i]);
    deb.push_back(arr[1][i]);
    deb.push_back(arr[2][i]);
  }
  */

  /**/ debug << "Unmerge Complete" << endl;

  // ===== Change Permutation =====
  perm = OBJ_LEN*n;
  p=0;
  calc(calc, m, n+m-1); p -- ;
  applyperm(applyperm, m, n+m-1);

  /**/ debug << "Change Permutation Complete" << endl;

  // ===== Output Answer =====
  for(int i=0; i<n; i++) {
    int ans = arr[2][m+i];
    FOR_NUM(j) outputs_circuit[i][j] = ans + j;
  }

  /**/ debug << "Solve Complete" << endl;

  return cur;
}
/*
s = (s & eq) | num

s = 0  -->  aa = a

(a & !s) | (b & s);

*/

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