#966034 (C++14) No.2025 Select $k$-th Submultiset

提出ソース

結果

問題	No.2025 Select $k$-th Submultiset
ユーザー	👑 hos.lyric
提出日時	2024-03-30 13:40:05
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	119 ms / 2,000 ms
コード長	4,370 bytes
コンパイル時間	1,077 ms
コンパイル使用メモリ	114,592 KB
実行使用メモリ	17,588 KB
最終ジャッジ日時	2024-03-30 13:40:14
合計ジャッジ時間	8,540 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 16,280 KB
testcase_01	AC	5 ms 16,280 KB
testcase_02	AC	5 ms 16,280 KB
testcase_03	AC	92 ms 17,588 KB
testcase_04	AC	83 ms 17,588 KB
testcase_05	AC	119 ms 17,588 KB
testcase_06	AC	100 ms 17,588 KB
testcase_07	AC	100 ms 17,588 KB
testcase_08	AC	106 ms 17,588 KB
testcase_09	AC	111 ms 17,588 KB
testcase_10	AC	114 ms 17,588 KB
testcase_11	AC	111 ms 17,588 KB
testcase_12	AC	119 ms 17,588 KB
testcase_13	AC	91 ms 17,588 KB
testcase_14	AC	101 ms 17,588 KB
testcase_15	AC	113 ms 17,588 KB
testcase_16	AC	110 ms 17,588 KB
testcase_17	AC	104 ms 17,588 KB
testcase_18	AC	113 ms 17,588 KB
testcase_19	AC	114 ms 17,588 KB
testcase_20	AC	111 ms 17,588 KB
testcase_21	AC	102 ms 17,588 KB
testcase_22	AC	112 ms 17,588 KB
testcase_23	AC	109 ms 17,588 KB
testcase_24	AC	103 ms 17,588 KB
testcase_25	AC	5 ms 16,280 KB
testcase_26	AC	5 ms 16,280 KB
testcase_27	AC	5 ms 16,280 KB
testcase_28	AC	4 ms 16,284 KB
testcase_29	AC	5 ms 16,280 KB
testcase_30	AC	5 ms 16,280 KB
testcase_31	AC	4 ms 16,284 KB
testcase_32	AC	5 ms 16,280 KB
testcase_33	AC	5 ms 16,280 KB
testcase_34	AC	5 ms 16,280 KB
testcase_35	AC	5 ms 16,280 KB
testcase_36	AC	6 ms 16,288 KB
testcase_37	AC	6 ms 16,284 KB
testcase_38	AC	5 ms 16,284 KB
testcase_39	AC	5 ms 16,284 KB
testcase_40	AC	4 ms 16,280 KB
testcase_41	AC	5 ms 16,280 KB
testcase_42	AC	4 ms 16,280 KB
testcase_43	AC	5 ms 16,280 KB
testcase_44	AC	5 ms 16,280 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード