If $$$n=1$$$, There is only one possible $$$\it{Lucky \ array}$$$. It is guaranteed that the given array is $$$\it{Lucky \ array}$$$ so there is no other $$$\it{Lucky \ array}$$$ to output. Hence the answer is $$$-1$$$.

For $$$n>1$$$, it is easy to see that there are more than one possible $$$\it{Lucky \ array}$$$. So we can use the following pattern to construct the $$$\it{Lucky \ array}$$$ :

$$$ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ ....$$$

If this constructed array is equal to the given array then we can swap the elements in $$$2^{nd}$$$ and $$$3^{rd}$$$ positions if $$$n>2$$$, otherwise we can just set the $$$2^{nd}$$$ to $$$0$$$.

Note that there are many possible constructions, the above mentioned is one of them

Time Complexity : $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];
        if(n==1) cout<<"-1\n";
        else if(n==2){
            if(a[1]==1) cout<<"0 0\n";
            else cout<<"0 1\n";
        }
        else{
            vector<int> b(n,0);
            for(int i=1;i<n;i+=2) b[i]=1;
            if(a==b) swap(b[1],b[2]);
            for(auto i:b) cout<<i<<" ";
            cout<<"\n";
        }
    }
}

Let's call array $$$c$$$ good if it contains non-positive integers. Now our task is to make array $$$c$$$ good using minimum number of given operations.

It is always optimal to choose the largest element in $$$c$$$ and decrease it by $$$a$$$ and decrease all other elements by $$$b$$$ until array $$$c$$$ becomes good. But this solution is very slow. We can optimise the solution by using the fact that if we can make the array good using $$$x$$$ operations then we can definitely make the array good using $$$x+1$$$ operations because if all elements in the array are non-positive then using extra operation will not make any element positive. So we can use binary search on our answer.

Binary search follows for fixed $$$m$$$ like decrease all elements by $$$bm$$$ and decrease the remaining positive elements by $$$(a-b)$$$ until it becomes non-positive, call these as extra operations, if the extra operations are not greater than $$$m$$$ decrease the upper bound of the answer, otherwise increase the lower bound of the answer.

Time Complexity : $$$O(nlog(\frac{M}{b}))$$$. where $$$M$$$ is the maximum element in the array $$$c$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,a,b;
        cin>>n>>a>>b;
        vector<ll> v(n);
        for(ll i=0;i<n;i++) cin>>v[i];
        ll l=0,r=1e9,ans=1e9;
        while(l<=r){
            ll m=(l+r)/2;
            ll ops=0;
            for(ll i=0;i<n;i++){
                if(v[i]>b*m){
                    ops+=((v[i]-b*m+(a-b-1))/(a-b));
                }
            }
            if(ops<=m){
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
        cout<<ans<<"\n";
    }
}

We can observe that for an index $$$i$$$, if $$$mex(h_1,h_2,\ldots,h_i)=0(h_j>0$$$ for all $$$1\le j \le i)$$$, the game will end after choose $$$x∈[1,max(h_1,h_2,\ldots,h_i)]$$$.

We can greedily consider the smallest index $$$i+1$$$ such that $$$mex(h_1,h_2,\ldots,h_i)=0(h_j>0$$$ for all $$$1\le j \le i)$$$ and $$$h_{i+1}>1+max(h_1,h_2,\ldots,h_i)]$$$.

We want to decrease $$$h_i$$$ with as many operations as possible, so we pick $$$x=1+max(h_1,h_2,\ldots,h_i)$$$ until $$$h_{i+1}\ge 1+max(h_1,h_2,\ldots,h_i)$$$.

A corner case is $$$h_{i+1}=k \cdot (1+max(h_1,h_2,\ldots,h_i))(k>1)$$$, when $$$h_{i+1}=2 \cdot (1+max(h_1,h_2,\ldots,h_i))$$$ we can pick $$$x=(2+max(h_1,h_2,\ldots,h_i))$$$ to make $$$h_{i+1}<1+max(h_1,h_2,\ldots,h_i)$$$, such that $$$max(h_1,h_2,\ldots,h_{i+1})=max(h_1,h_2,\ldots,h_i)$$$.

Run the greedy process in sequence.

Time Complexity : $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        ll ans=0,val=1;
        for(ll i=0;i<n;i++){
            ll res=(a[i]-1)/val;
            if(res>0){
                ans+=res;
                a[i]=1;
            }
            if(val==a[i]) val++;
        }
        ans++;
        cout<<ans<<"\n";
    }
}

An important observation is that the answer always takes the following form：

$$$sig_1 \cdot 1+sig_2 \cdot 2+\ldots+sig_n \cdot n$$$, where $$$sig_i=1$$$ or $$$-1$$$ and $$$-n<\Sigma_{i=1}^{n} sig_i<n$$$

We will provide the construction method later. Firstly, we need to find $$$sig_1,sig_2,\ldots,sig_n$$$ such that $$$sig_1 \cdot 1+sig_2 \cdot 2+\ldots+sig_n \cdot n=m$$$. We can see for $$$-\frac{n(n+1)}{2}+1<m<\frac{n(n+1)}{2}-1$$$ it is always possible. The construction is to find the minimum $$$i$$$ such that $$$1+2+\dots+i \ge m$$$, then set $$$sig_1,sig_2,\ldots,sig_i$$$ to $$$1$$$ and set $$$sig_{i+1},sig_{i+2},\ldots,sig_n$$$ to $$$-1$$$. After that, if $$$delta=m-(1+2+\dots+i)>0$$$, swap $$$sig_{i}$$$ andd $$$sig_{delta}$$$.

Now we have decided on the symbol for each number. Let's say we have some numbers $$$posi_1,posi_2,\ldots,posi_x$$$ and $$$nega_1,nega_2,\ldots,nega_y(x+y=n)$$$. The construction for $$$S={m}$$$ is to make $$$A=posi_1-nega_2-nega_3-\ldots-nega_y$$$ and $$$B=nega_1-posi_2-posi_3-\ldots-posi_x$$$, then do $$$A-B$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T;
ll  n,m;
int tag[N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%I64d%I64d",&n,&m);
		ll mx=n*(n+1)/2-2,mn=-mx,sum=mn,cur1,cur2;
		vector<ll> v[2];
		if(m<mn||m>mx||((mx&1)^(m&1)))
		{
			printf("NO\n");
			continue;
		}
		printf("YES\n");
		tag[1]=1;
		for(int i=2;i<=n;i++) tag[i]=0;
		for(int i=2;i<=n;i++)
		{
			tag[i]=1;
			sum+=2*i;
			if(sum>=m)
			{
				tag[(sum-m)/2]=0;
				break;
			}
		}
		for(int i=1;i<=n;i++) v[tag[i]].push_back(i);
		cur1=v[1][0];
		for(int i=1;i<v[0].size();i++) 
		{
			printf("%I64d %I64d\n",cur1,v[0][i]);
			cur1-=v[0][i];
		}
		cur2=v[0][0];
		for(int i=1;i<v[1].size();i++) 
		{
			printf("%I64d %I64d\n",cur2,v[1][i]);
			cur2-=v[1][i];
		}
		printf("%I64d %I64d\n",cur1,cur2);
	}
	
	//fclose(stdin);
	return 0;
}

We can see the maximum of $$$f(p,q)$$$ is $$$2\cdot(n+(n-1)+\ldots+\frac{n}{2}+1)-2\cdot(\frac{n}{2}+\ldots+2+1)$$$.

let $$$x=\frac{n}{2}$$$, To maximize the value of $$$f(p,q)$$$ we have to set the permutation $$$q$$$ such that $$$p_{q_{i}}<=x$$$ for odd values of $$$i$$$ and $$$p_{q_{i}}>x$$$ for even values of $$$i$$$.

So now our task is simplified as find whether each element is $$$<=x$$$ or $$$>x$$$.

For that we have to do some observations on a permutation that there will be a index $$$i$$$ such median($$$i+1,i+2,...,i+\frac{n}{2}$$$)$$$<=x$$$ and median($$$i+2,i+3,...,i+\frac{n}{2}+1$$$)$$$>x$$$ and vice-versa. we can find this by binary search using $$$log(x)$$$ queries. Now $$$p_{i+1}<=x$$$ and $$$p_{i+\frac{n}{2}+1}>x$$$ and vice-versa.

Later we can check other elements using this $$$2$$$ elements.

For every element with index $$$j=i+2,i+3,....,i+\frac{n}{2}$$$ we can check by asking following type of query

$$$? \ 1 \ 2 \ .... \ i \ j \ (i+\frac{n}{2}+2) \ (i+\frac{n}{2}+3) n$$$

For every remaining indices $$$j$$$ we can check by asking following type of query

$$$? \ j \ (i+2) \ (i+3) \ .....\ (i+\frac{n}{2})$$$

So total queries used are $$$n+log(x)$$$ which are less than $$$n+30$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int n;
 
int query(vector<int> v){
    cout<<"? ";
    for(int i=0;i<(int)v.size();i++) cout<<v[i]+1<<" ";
    cout<<endl;
    int x;
    cin>>x;
    if(x>(n/2)) return 1;
    return 0;
}
 
int sol(int j){
    vector<int> v(n/2);
    for(int i=0;i<n/2;i++) v[i]=i+j;
    return query(v);
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        cin>>n;
        int l=0,r=n/2;
        int vl=sol(0),vr=sol(n/2);
        while(l+1<r){
            int m=(l+r)/2;
            int vm=sol(m);
            if(vm==vl) l=m;
            else r=m;
        }
        vector<int> v2,v3;
        for(int i=r;i<(r+(n/2)-1);i++){
            v2.push_back(i);
            v3.push_back((i+(n/2))%n);
        }
        vector<int> ans(n);
        ans[l]=vl;
        ans[l+(n/2)]=vr;
        for(int i=0;i<(int)v2.size();i++){
            vector<int> v=v3;
            v.push_back(v2[i]);
            ans[v2[i]]=query(v);
        }
        for(int i=0;i<(int)v3.size();i++){
            vector<int> v=v2;
            v.push_back(v3[i]);
            ans[v3[i]]=query(v);
        }
        vector<int> even,odd;
        for(int i=0;i<n;i++){
            if(ans[i]==0) even.push_back(i+1);
            else odd.push_back(i+1);
        }
        cout<<"! ";
        for(int i=0;i<(int)even.size();i++){
            cout<<even[i]<<" ";
            cout<<odd[i]<<" ";
        }
        cout<<endl;
    }
}

coming soon...

coming soon...