Cerinta completa

Lena developed a sorting algorithm described by the following pseudocode:

lena_sort(array nums) {
    if (nums.size <= 1) {
        return nums;
    }
    pivot = nums[0];
    array less;
    array more;
    for (i = 1; i < nums.size; ++i) {
    	// Comparison
        if (nums[i] < pivot) {
            less.append(nums[i]);
        }
        else {
            more.append(nums[i]);
        }
    }
    sorted_less = lena_sort(less);
    sorted_more = lena_sort(more);
    ans = sorted_less + pivot + sorted_more;
    
    return ans;
}

We consider a comparison to be any time some is compared with .

You must solve queries where each query consists of some and . For each query, construct an array of distinct elements in the inclusive range between and that will be sorted by in exactly comparisons, then print each respective element of the unsorted array as a single line of space-separated integers; if no such array exists, print -1 instead.

Input Format

The first line contains a single integer denoting (the number of queries).
Each line of the subsequent lines contains two space-separated integers describing the respective values of (the length of the array) and (the number of comparisons) for query .

Constraints

  • the sum of over all queries

Output Format

Print the answer to each query on a new line. For each query , print space-separated integers describing each respective element in an unsorted array that Lena’s algorithm will sort in exactly comparisons; if no such array exists, print -1 instead.

Sample Input 0

2
5 6
5 100

Sample Output 0

4 2 1 3 5
-1

Explanation 0

We perform the following queries:

  1. One array with elements is . The sequence of sorting operations looks like this:

    • Run on . Compare with , , , and for a total of comparisons. We’re then left with and ; we only need to continue sorting , as is sorted with respect to itself because it only contains one element.
    • Run on . Compare with and for a total of comparisons. We’re then left with and , so we stop sorting.

    We sorted in comparisons and , so we print 4 2 1 3 5 on a new line.

  2. It’s not possible to construct an array with elements that will sort in exactly comparisons, so we print -1 on a new line.

Sample Input 1

3
1 0
4 6
3 2

Sample Output 1

1
4 3 2 1
2 1 3

Explanation 1

We perform the following queries:

  1. We want an array with element that sorts in comparisons; any array with element is already sorted (i.e., performs comparisons), so we choose as our array and print 1 on a new line.

  2. One array with elements is ; sorting it with looks like this:

    • on . Compare with , , and for a total of comparisons. We’re then left with and ; we only need to continue sorting , as is empty.
    • Run on . Compare with and for a total of comparisons. We’re then left with and , so we only continue sorting .
    • Run on . Compare with for a total of comparison. We then stop sorting, as and .

    We sorted in comparisons and , so we print 4 3 2 1 on a new line.

  3. One array with elements is . When we run on it, we compare with and for a total of comparisons. We’re then left with and , so we stop sorting.

    We sorted in comparisons and , so we print 2 1 3 on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }
vector<string> s_p_l_i_t(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while(getline(ss,x,c)) v.emplace_back(x); return move(v);}
void e_r_r(vector<string>::iterator it) {}
template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}
const ll MOD=1e9+7;

ll mn[112345],mx[112345];

vector<int> dfs(int n,int m){
  if(n==0) return {};
  if(n==1) return {1};
  m-=n-1;
  //out(n,m,1);
  rep(i,n){
    if(mn[i] + mn[n-1-i] <= m && m <= mx[i] + mx[n-1-i]){
      int t;
      if(mn[n-1-i] <= m-mn[i] && m-mn[i] <= mx[n-1-i]){
	t=mn[i];
      }else{
	t=m-mx[n-1-i];
      }
      vector<int> l=dfs(i,t);
      vector<int> r=dfs(n-1-i,m-t);
      if(l.size()!=i || r.size()!=n-1-i) for(;;);
      int p=i+1;
      //out(i,t,p,l,r,1);
      vector<int> re{p};
      for(int x:l) re.pb(x);
      for(int x:r) re.pb(x+p);
      return re;
    }
  }
  //out(mn[n],mx[n],1);
  //cout<<"!"<<endl;
  for(;;);
  return vector<int>(n,-1);
}

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  mn[0]=mn[1]=mx[0]=mx[1]=0;
  reps(i,2,102345){
    mn[i]=mn[i/2]+mn[(i-1)/2]+i-1;
    mx[i]=mx[i-1]+i-1;
  }
  //rep(i,10) cout<<pii(mn[i],mx[i]);cout<<Endl;
  int T;
  cin>>T;
  while(T--){
    int n,m;
    cin>>n>>m;
    if(m<mn[n] || mx[n]<m){
      cout<<-1<<endl;
      continue;
    }
    int mm=m,nn=n;
    vector<int> re;
    while(nn){
      if(mm-(nn-1)<mn[nn-1]) break;
      re.pb(nn);
      mm-=nn-1; --nn;
    }
    auto tmp=dfs(nn,mm);
    for(int x:tmp) re.pb(x);
    rep(i,n){
      if(i) cout<<" ";
      cout<<re[i];
    }
    cout<<endl;
    if(re.size()!=n) for(;;);
  }
  return 0;
}

Scor obtinut: 1.0

Submission ID: 464650204

Link challenge: https://www.hackerrank.com/challenges/lena-sort/problem

Lena Sort