fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. using i128 = __int128_t;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int T;
  10.     if(!(cin >> T)) return 0;
  11.     while(T--){
  12.         int N;
  13.         int64 K;
  14.         cin >> N >> K;
  15.  
  16.         // precompute pow2 up to N (as i128), but cap growth limited
  17.         vector<i128> pow2(N+2);
  18.         pow2[0] = 1;
  19.         for(int i=1;i<=N+1;i++){
  20.             pow2[i] = pow2[i-1] * 2;
  21.             // don't cap; i128 will hold until very large, division will handle it
  22.         }
  23.  
  24.         // helper: compute max possible sum S for a given X
  25.         auto maxSumForX = [&](int64 X)->i128{
  26.             if(X <= 0) return (i128)0;
  27.             i128 cap = (i128)X - 1; // cap = X-1
  28.             if(cap <= 0) return (i128)0;
  29.  
  30.             i128 best = 0;
  31.             // m from 0 .. N-2 (cases where we stop before using all N-1 steps)
  32.             for(int m=0; m <= max(0, N-2); ++m){
  33.                 // B range: (floor(cap / 2^{m+1}) + 1) .. floor(cap / 2^{m})
  34.                 i128 d1 = pow2[m+1];
  35.                 i128 d2 = pow2[m];
  36.                 i128 Bmin = (cap / d1) + 1;
  37.                 i128 Bmax = (cap / d2);
  38.                 if(Bmin <= Bmax && Bmax >= 1){
  39.                     if(Bmin < 1) Bmin = 1;
  40.                     // For this region, maximum S achieved at smallest B (S = X-1 - B)
  41.                     i128 S = (i128)X - 1 - Bmin;
  42.                     if(S > best) best = S;
  43.                 }
  44.                 // if d2 > cap and Bmax==0 then no valid B here
  45.             }
  46.             // m = N-1 case: all steps are full doubling (if possible)
  47.             if(N-1 >= 0){
  48.                 i128 d = pow2[N-1];
  49.                 if(d > 0){
  50.                     i128 B = cap / d; // floor
  51.                     if(B >= 1){
  52.                         i128 S = (pow2[N-1] - 1) * B;
  53.                         if(S > best) best = S;
  54.                     }
  55.                 }
  56.             }
  57.             return best;
  58.         };
  59.  
  60.         // binary search minimal X in [1, K+1] (upper bound: A_N at most A1 + K, A1>=1)
  61.         int64 lo = 1, hi = K + 1; // inclusive search for minimal feasible X
  62.         while(lo < hi){
  63.             int64 mid = lo + (hi - lo) / 2;
  64.             i128 s = maxSumForX(mid);
  65.             if(s >= (i128)K) hi = mid;
  66.             else lo = mid + 1;
  67.         }
  68.         int64 X = lo;
  69.  
  70.         // Now we must construct a sequence A of length N with A_N == X (or <=X but we use <=X and minimal X)
  71.         // Approach: try candidate starting A1 values (represented as B = A1 - 1)
  72.         // Candidate B's: Bmin/Bmax boundaries for m, plus ceil(K/(2^{N-1}-1)) candidate, plus small B fallback
  73.         vector<int64> candidatesB;
  74.         i128 cap = (i128)X - 1;
  75.         if(cap >= 1){
  76.             for(int m=0; m <= max(0, N-2); ++m){
  77.                 i128 d1 = pow2[m+1];
  78.                 i128 d2 = pow2[m];
  79.                 i128 Bmin = (cap / d1) + 1;
  80.                 i128 Bmax = (cap / d2);
  81.                 if(Bmin <= Bmax && Bmax >= 1){
  82.                     if(Bmin < 1) Bmin = 1;
  83.                     // push both endpoints as candidates
  84.                     candidatesB.push_back((int64)Bmin);
  85.                     candidatesB.push_back((int64)min<i128>(Bmax, (i128)2e9));
  86.                 }
  87.             }
  88.             // m = N-1 candidate: choose ceil(K / (2^{N-1}-1))
  89.             if(N-1 >= 0){
  90.                 i128 denom = (pow2[N-1] - 1);
  91.                 if(denom > 0){
  92.                     i128 needB = ( (i128)K + denom - 1 ) / denom; // ceil
  93.                     if(needB >= 1 && needB <= cap) candidatesB.push_back((int64)needB);
  94.                 }
  95.             }
  96.             // some small Bs fallback (bounded by problem constraints)
  97.             int64 limitFallback = (int64)min<i128>(cap, (i128)200000);
  98.             for(int64 b=1; b<=limitFallback; ++b) candidatesB.push_back(b);
  99.         }
  100.         // add B=0 possibility (A1=1) too
  101.         candidatesB.push_back(0);
  102.  
  103.         // unique candidates
  104.         sort(candidatesB.begin(), candidatesB.end());
  105.         candidatesB.erase(unique(candidatesB.begin(), candidatesB.end()), candidatesB.end());
  106.  
  107.         // A helper: given B (=A1-1) and X produce sequence greedily and return sum produced and sequence
  108.         auto tryBuild = [&](int64 B)->pair<i128, vector<int64>>{
  109.             vector<int64> A;
  110.             A.reserve(N);
  111.             int64 a1 = B + 1;
  112.             A.push_back(a1);
  113.             i128 rem = K;
  114.             i128 cur = a1;
  115.             for(int i=1;i<=N-1;i++){
  116.                 if(cur > (i128)X){
  117.                     // impossible path
  118.                     return make_pair((i128)-1, vector<int64>());
  119.                 }
  120.                 // compute r_max for this cur with cap X
  121.                 i128 rmax;
  122.                 if((i128)X >= 2*cur - 1) rmax = cur - 1;
  123.                 else rmax = (i128)X - cur; // >=0 if cur<=X
  124.                 if(rmax < 0) rmax = 0;
  125.                 i128 take = rmax;
  126.                 if(take > rem) take = rem;
  127.                 i128 nxt = cur + take;
  128.                 if(nxt > (i128)X) nxt = X; // safety
  129.                 A.push_back((int64)nxt);
  130.                 rem -= take;
  131.                 cur = nxt;
  132.             }
  133.             return make_pair((i128)(K - rem), A); // returned sum actually produced
  134.         };
  135.  
  136.         vector<int64> answer;
  137.         bool found = false;
  138.         for(int64 B : candidatesB){
  139.             if(B < 0) continue;
  140.             if((i128)B > cap) continue;
  141.             auto res = tryBuild(B);
  142.             i128 produced = res.first;
  143.             if(produced >= (i128)K){
  144.                 // we have a valid construction (greedy may produce exactly K; if produced > K that's impossible because greedy never overshoots)
  145.                 // but produced should equal K (since we restricted take<=rem). So produced==K
  146.                 answer = res.second;
  147.                 found = true;
  148.                 break;
  149.             }
  150.         }
  151.  
  152.         // As a last resort (shouldn't be needed), try brute force A1 from 1..min(X, 200000)
  153.         if(!found){
  154.             int64 limit = (int64)min<i128>((i128)X, (i128)200000);
  155.             for(int64 a1 = 1; a1 <= limit && !found; ++a1){
  156.                 auto res = tryBuild(a1 - 1);
  157.                 if(res.first >= (i128)K){
  158.                     answer = res.second;
  159.                     found = true;
  160.                     break;
  161.                 }
  162.             }
  163.         }
  164.  
  165.         if(!found){
  166.             // Should not happen for a correct algorithm; fallback create trivial increasing sequence with last X
  167.             // But to be safe, output fallback (1,1,...,X)
  168.             answer.assign(N, 1);
  169.             answer[N-1] = X;
  170.         }
  171.  
  172.         // ensure output length N
  173.         if((int)answer.size() != N){
  174.             // If our built vector shorter/longer, pad appropriately (should not happen)
  175.             vector<int64> tmp;
  176.             tmp.reserve(N);
  177.             for(int i=0;i<N;i++){
  178.                 if(i < (int)answer.size()) tmp.push_back(answer[i]);
  179.                 else tmp.push_back(answer.back());
  180.             }
  181.             answer.swap(tmp);
  182.         }
  183.  
  184.         // Print
  185.         for(int i=0;i<N;i++){
  186.             if(i) cout << ' ';
  187.             cout << answer[i];
  188.         }
  189.         cout << '\n';
  190.     }
  191.     return 0;
  192. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
2
5 3
2 3
stdout 
1 1 1 1 4
1 4
https://ideone.com/dWoQtk
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 hours 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!