Submission #930443

#	Time	Username	Problem	Language	Result	Execution time	Memory
930443		chrislaiisme	Alice, Bob, and Circuit (APIO23_abc)	C++17	12 / 100	800 ms	328640 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) {}
};

vector<int> Vec;
string Str = "";
void Perm(int l, int r) {
  // debug << l << ' ' << r << endl;
  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) {
      if(b == l+len-1 && n%2 == 1) swap(a, b);
      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(l, l+len-1);
  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(l+len, r);
  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);
  }
  // debug << " Convert to Object " << endl;
  // =============== 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;
  Vec = perm, Str.clear();
  Perm(0, n-1);
  Ydown_Init = Str;
  // debug << Ydown_Init << endl;
  // debug << "Get Pemutation of 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;
  // debug << "Sort vec and Pass Data to Circuit (Xup + Ydown_Init)" << endl;
  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<pair<pii, int> > sorted(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);
    sorted[i].F = make_pair(s, r);
  }

  // =============== Get Pemutation of Xdown -> Yup ===============
  vector<int> perm(m);
  sort(all(sorted), [&](pair<pii, int> a, pair<pii, int> b) {if(a.F.S != b.F.S) return a.F.S < b.F.S; return a.F.F < b.F.F;});
  for(int i=0; i<m; i++) sorted[i].S = i;
  sort(all(sorted), [&](pair<pii, int> a, pair<pii, int> b) {if(a.F.F != b.F.F) return a.F.F > b.F.F; return a.F.S > b.F.S;});
  for(int i=0; i<m; i++) perm[i] = sorted[i].S;
  // for(int i=0; i<m; i++) debug << perm[i] << ' ';
  // debug << " !!!!! " << endl;
  string Xdown_Yup = "";
  Vec = perm, Str.clear();
  Perm(0, m-1);
  Xdown_Yup = Str;
  // 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++] = (sorted[i].F.F >> j) & 1;
    outputs_bob[cur++] = 0;
    for(int j=0; j<NAME_LEN-1; j++)
      outputs_bob[cur++] = (sorted[i].F.S >> j) & 1;
    FOR_NUM(j)
      outputs_bob[cur++] = 0;
  }
  // debug << Xdown_Yup << " ??? " << 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 one = op(OP_ONE, 1, 1);
  int ZERO = cur;
  FOR_NUM(i) op(OP_ZERO, 0, 0);
  int ZERO_NAME = cur;
  FOR_NAME(i) op(OP_ZERO, 0, 0);
  int INF = cur;
  FOR_NUM(i) op(OP_ONE, 1, 1);
  int INF_NAME = cur;
  FOR_NAME(i) op(OP_ONE, 1, 1);

  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;
  int SIZE = 1;
  while(SIZE < n+m) SIZE *= 2;
  vector<vector<int> > arr(3, vector<int>(SIZE)); // 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][SIZE-m+i] = la+OBJ_LEN*i;
    arr[1][SIZE-m+i] = arr[0][SIZE-m+i] + NAME_LEN;
    arr[2][SIZE-m+i] = arr[1][SIZE-m+i] + NAME_LEN;
  }
  for(int i=n; i<SIZE-m; i++) {
    arr[0][i] = INF_NAME;
    arr[1][i] = INF_NAME;
    arr[2][i] = INF;
  }

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

  auto swap = [&](int a, int b, int s) {
    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;
        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;
    }
  };

  auto cmp = [&](int a, int b, int k) {
    int s = zero;
    int P = arr[k][a], Q = arr[k][b];
    if(Q == INF) {
      signals.push_back(zero);
      return;
    }
    if(P == INF) {
      signals.push_back(one);
      swap(a, b, one);
      return;
    }
    FOR_NAME(i) {
      int p = P+i, q = Q+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++) cmp(i, i+len, k);
    merge1(merge1, l, m, k); merge1(merge1, m+1, r, k);
  };
  merge(merge, 0, SIZE-1, 0);
  
  // deb = signals;
  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, SIZE-1);
  /*
  for(int i=0; i<SIZE; 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 =====
  int perm = la + OBJ_LEN*m;
  p=0;
  auto applyperm = [&](auto applyperm1, int l, int r) {
    if(l >= r) return;
    int num = r-l+1, len = (num+1)/2;

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

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

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

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

  // ===== Add Number to Person =====
  signals.clear();
  merge(merge, 0, SIZE-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;
  }
  /*
  for(int i=0; i<SIZE; i++) {
    deb.push_back(arr[0][i]);
    deb.push_back(arr[1][i]);
    deb.push_back(arr[2][i]);
  }
  */
  // deb = signals;
  /**/ debug << "Add Number to Person Complete" << endl;

  // ===== Unmerge =====
  reverse(all(signals));
  p=0;
  unmerge(unmerge, 0, SIZE-1);

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

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

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

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

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

  return cur;
}
/*
  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]);
  }
*/

Compilation message (stderr)

abc.cpp: In function 'int circuit(int, int, int*, int (*)[2], int (*)[16])':
abc.cpp:253:7: warning: unused variable 'ZERO_NAME' [-Wunused-variable]
  253 |   int ZERO_NAME = cur;
      |       ^~~~~~~~~

• 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