fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef pair<int, int> pii;
  7. typedef pair<ll, ll> pll;
  8. typedef vector<int> vi;
  9. typedef vector<ll> vll;
  10. typedef string str;
  11.  
  12. #define pb push_back
  13. #define mp make_pair
  14. #define fi first
  15. #define se second
  16. #define all(x) (x).begin(), (x).end()
  17. #define len(x) ((int)(x).size())
  18. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  19. #define forr(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
  20. #define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)
  21. #define cmin(a, b) a = min(a, b)
  22. #define cmax(a, b) a = max(a, b)
  23.  
  24. void solve() {
  25.     int n;
  26.     cin >> n;
  27.  
  28.     auto check = [&](int M) {
  29.         ll sum = 0;
  30.         forr(i, 1, n) sum += 1LL * i * (M / i);
  31.         return sum >= n;
  32.     };
  33.  
  34.     int low = 1, high = n, ans = n;
  35.     while (low <= high) {
  36.         int mid = low + (high - low) / 2;
  37.         if (check(mid)) {
  38.             ans = mid;
  39.             high = mid - 1;
  40.         } else {
  41.             low = mid + 1;
  42.         }
  43.     }
  44.  
  45.     cout << ans << "\n";
  46.  
  47.     vi a;
  48.     int bag = 1;
  49.     ford(i, n, 1) {
  50.         int limit = ans / i;
  51.         while (limit-- > 0 && len(a) + i <= n) {
  52.             forn(j, i) a.pb(bag);
  53.             bag++;
  54.         }
  55.     }
  56.     while (len(a) < n) {
  57.         a.pb(bag++);
  58.     }
  59.  
  60.     forn(i, n) {
  61.         cout << a[i] << (i == n - 1 ? "" : " ");
  62.     }
  63.     cout << "\n";
  64. }
  65.  
  66. int main() {
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69.  
  70.     int t;
  71.     if (cin >> t) {
  72.         while (t--) {
  73.             solve();
  74.         }
  75.     }
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 5348KB
comments (?)
stdin
copy 
3
4
5
8
stdout
copy 
2
1 1 2 3
3
1 1 1 2 2
3
1 1 1 2 2 3 4 5
https://ideone.com/hnL60D
language:
C++14 (gcc 8.3)
created:
48 minutes ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!