#1166684 (C++23) No.3562 Communicate Sorted Vector

• 問題: No.3562 Communicate Sorted Vector
• ユーザー: soryuusi0219
• 提出日時: 2026-05-25 19:49:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 82 ms / 2,000 ms
• コード長: 5,432 bytes
• コンパイル時間: 3,493 ms
• コンパイル使用メモリ: 353,420 KB
• 実行使用メモリ: 30,320 KB
• 平均クエリ数: 3.00
• 最終ジャッジ日時: 2026-05-29 18:39:38
• 合計ジャッジ時間: 25,682 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

サブタスク	配点	結果
部分点1	10 %	AC * 45
部分点2	25 %	AC * 45
部分点3	65 %	AC * 46
合計	100 点

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
template<class T, class U> bool chmin(T& a, U b) { return a > b ? a = b, 1 : 0; }
template<class T, class U> bool chmax(T& a, U b) { return a < b ? a = b, 1 : 0; }
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using vvll = vector<vll>;
#define _O(_1, _2, _3, n, ...) n
#define _r1(i, n) for(ll i = 0; i < (ll)(n); i++)
#define _r2(i, l, r) for(ll i = (ll)(l); i < (ll)(r); i++)
#define rep(...) _O(__VA_ARGS__, _r2, _r1)(__VA_ARGS__)
#define _rr1(i, n) for(ll i = (ll)(n) - 1; i >= 0; i--)
#define _rr2(i, l, r) for(ll i = (ll)(r) - 1; i >= (ll)(l); i--)
#define rrep(...) _O(__VA_ARGS__, _rr2, _rr1)(__VA_ARGS__)
template<class T, class U> ostream& operator<<(ostream& o, const pair<T,U>& p) {
   return  o << "(" << p.first << "," << p.second << ")";
}
template<class T> ostream& operator<<(ostream& o, const vector<T>& v) {
   ll i = 0;
   for(auto& x : v) o << (i++ ? " " : "") << x;
   return o;
}
template<class H, class... T> void out(const H& h, const T&... t) {
   cout << h;
   ((cout << " " << t), ...);
   cout << endl;
}

struct BigInt{
  static constexpr ll B = 100'000'000;
  static constexpr ll T = 16;
  array<ll,T> v;
  BigInt() {fill(all(v),0);}
  BigInt(ll x) {fill(all(v),0); v[0] = x; reduce();}
  void reduce(){
    rep(i,T-1){
      v[i+1] += v[i] / B;
      v[i] %= B;
      if(v[i] < 0) v[i] += B, --v[i+1];
    }
  }
  friend BigInt operator+=(BigInt& a, const BigInt& b) { rep(i,T) a.v[i] += b.v[i]; a.reduce(); return a; }
  friend BigInt operator-=(BigInt& a, const BigInt& b) { rep(i,T) a.v[i] -= b.v[i]; a.reduce(); return a; }
  friend BigInt operator*=(BigInt& a, ll b) { rep(i,T) a.v[i] *= b; a.reduce(); return a; }
  friend BigInt operator/=(BigInt& a, ll b) {
    rrep(i,T) {
      if(i) a.v[i-1] += (a.v[i] % b) * B;
      a.v[i] /= b;
    }
    return a;
  }
  friend BigInt operator+(BigInt a, const BigInt& b) { return (a += b); }
  friend BigInt operator-(BigInt a, const BigInt& b) { return (a -= b); }
  friend BigInt operator*(BigInt a, ll b) { return (a *= b); }
  friend BigInt operator/(BigInt a, ll b) { return (a /= b); }
  
  friend bool operator==(const BigInt& a, const BigInt& b) { return a.v == b.v; }
  friend bool operator<(const BigInt& a, const BigInt& b) { 
    rrep(i,T){
      if(a.v[i] < b.v[i]) return true;
      if(a.v[i] > b.v[i]) return false;
    }
    return false;
  }
  friend bool operator>(const BigInt& a, const BigInt& b) { 
    rrep(i,T){
      if(a.v[i] > b.v[i]) return true;
      if(a.v[i] < b.v[i]) return false;
    }
    return false;
  }

  BigInt operator-() const { return BigInt(0)-(*this); }
  friend ostream& operator<<(ostream& os, const BigInt& a) { 
    ll x = T-1;
    while(x && !a.v[x]) --x;
    os << a.v[x--];
    while(x >= 0) os << std::setw(8) << std::setfill('0') << a.v[x--];
    return os;
  }
};

BigInt encode_vector(ll n, vll a){
  if(!n) return 0;
  rep(i,n) a[i] -= i+1;
  BigInt x;
  rep(i,n) if(a[i]){
    BigInt y = 1;
    rep(j,i+1) y *= a[i]+j;
    rep(j,i+1) y /= j+1;
    x += y;
  }
  return x;
}

vll decode_vector(ll n, BigInt x){
  if(!n) return {};
  vll a(n);
  rrep(i,n) {
    ll ok = 0, ng = (i == n-1 ? 1000000010 : a[i+1]+1);
    while(ng - ok > 1){
      ll t = (ok + ng) / 2;
      BigInt y = 1;
      rep(j,i+1) y *= t+j;
      rep(j,i+1) y /= j+1;
      if(y > x) ng = t;
      else ok = t;
    }
    BigInt y = 1;
    rep(j,i+1) y *= ok+j;
    rep(j,i+1) y /= j+1;
    x -= y;
    a[i] = ok;
  }
  rep(i,n) a[i] += i+1;
  return a;
}

vector<string> encode_01(ll n, BigInt x){
  BigInt y = 1;
  for(ll q = 1; q; ++q){
    y *= 2;
    for(ll k = 1; k <= min(n,q); ++k){
      BigInt z = y;
      rep(i,k-1) z *= q-1-i; 
      rep(i,k-1) z /= 1+i;
      if(z > x){
        vector<bool> bit(q);
        rep(i,q){
          bit[i] = x.v[0]&1;
          x /= 2;
        }
        auto sep = decode_vector(k-1,x);
        vector<string> res(k);
        ll j = 0;
        rep(i,q){
          if(j < k-1 && i == sep[j]) ++j;
          res[j].push_back('0' + bit[i]);
        }
        cerr << q << endl;
        return res;
      }
      x -= z;
    }
  }
  return {};
}


BigInt decode_01(ll n, vector<string> s){
  ll k = s.size();
  ll q = 0;
  rep(i,k) q += s[i].size();
  BigInt x = 0, y = 1;
  for(ll q0 = 1; q0 < q; ++q0){
    y *= 2;
    for(ll k0 = 1; k0 <= min(n,q0); ++k0){
      BigInt z = y;
      rep(i,k0-1) z *= q0-1-i; 
      rep(i,k0-1) z /= 1+i;
      x += z;
    }
  }
  y *= 2;
  for(ll k0 = 1; k0 < k; ++k0){
    BigInt z = y;
    rep(i,k0-1) z *= q-1-i; 
    rep(i,k0-1) z /= 1+i;
    x += z;
  }
  vll sep(k);
  rep(i,k-1) sep[i] = s[i].size();
  rep(i,k-1) sep[i+1] += sep[i];
  auto z = encode_vector(k-1,sep);
  rrep(i,k) rrep(j,s[i].size()){
    z += z + (s[i][j] - '0');
  }
  return x + z;
}


void Alice(ll n){
  vll a(n);
  rep(i,n) cin >> a[i];
  auto x = encode_vector(n,a);
  auto s = encode_01(n,x);
  out(s.size());
  for(auto& t : s) out(t);

  auto y = decode_01(n,s);
  auto b = decode_vector(n,y);
  assert(a == b);
}

void Bob(ll n){
  ll k; cin >> k;
  vector<string> s(k);
  rep(i,k) cin >> s[i];
  auto y = decode_01(n,s);
  auto b = decode_vector(n,y);
  out(b);
}

int main(){
  string s;
  ll n, q;
  cin >> s >> n >> q;
  if(s == "Alice") Alice(n);
  else if(s == "Bob") Bob(n);
}