結果

問題 No.2025 Select $k$-th Submultiset
コンテスト
ユーザー hos.lyric
提出日時 2024-03-30 13:40:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 4,370 bytes
コンパイル時間 1,077 ms
コンパイル使用メモリ 114,608 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2024-09-30 17:29:03
合計ジャッジ時間 6,882 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


using INT = __int128;

int N, L;
int C[4];
int Q;
vector<INT> K;

INT dp[4][100'010], dpSum[4][100'010];
INT get(int i, int l, int r) {
  chmax(l, 0);
  chmin(r, L);
  return (l <= r) ? (dpSum[i][r + 1] - dpSum[i][l]) : 0;
}

int main() {
  for (; ~scanf("%d%d", &N, &L); ) {
    for (int i = 0; i < N; ++i) {
      scanf("%d", &C[i]);
    }
    scanf("%d", &Q);
    K.resize(Q);
    for (int q = 0; q < Q; ++q) {
      K[q] = inInt128();
    }
    
    memset(dp, 0, sizeof(dp));
    memset(dpSum, 0, sizeof(dpSum));
    for (int i = N; --i >= 0; ) {
      if (i == N - 1) {
        for (int x = 0; x <= L; ++x) {
          dp[i][x] = (x <= C[i]) ? 1 : 0;
        }
      } else {
        for (int x = 0; x <= L; ++x) {
          dp[i][x] = get(i + 1, x - C[i], x);
        }
      }
      for (int x = 0; x <= L; ++x) {
        dpSum[i][x + 1] = dpSum[i][x] + dp[i][x];
      }
// if(L<=100){cerr<<"dp["<<i<<"] = ";pv(dp[i],dp[i]+(L+1));}
    }
    
    for (int q = 0; q < Q; ++q) {
      if (K[q] > dp[0][L]) {
        puts("-1");
      } else {
        int ans[4] = {};
        INT k = K[q];
        int l = L;
        for (int i = 0; i < N - 1; ++i) {
          assert(k <= get(i, l - C[i], l));
          int lo = 0, hi = C[i] + 1;
          for (; lo + 1 < hi; ) {
            const int mid = (lo + hi) / 2;
            // ans[0] \in [mid, C[i]]
            ((k > get(i + 1, l - C[i], l - mid)) ? hi : lo) = mid;
          }
          ans[i] = lo;
          k -= get(i + 1, l - C[i], l - hi);
          l -= lo;
        }
        ans[N - 1] = l;
        for (int i = 0; i < N; ++i) {
          if (i) printf(" ");
          printf("%d", ans[i]);
        }
        puts("");
      }
    }
  }
  return 0;
}
0