make the first element $$$a_1 = lcm(1,2,\cdots,n-1)$$$ and the other $$$n-1$$$ elements $$$(1,2,3,...,n-1)$$$, then you will have $$$gcd(a_1,1) = 1$$$, $$$gcd(a_1,2) = 2$$$, $$$\cdots$$$ etc.

then the $$$mex$$$ is at least $$$n$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long

void solve()
{
    int n;
    cin>>n;
    if(n==1)
    {
        cout<<0<<endl;
        return;
    }
    ll x=1;
    cout<<n<<endl;
    for(ll i=1; i<n; i++)
    {
        cout<<i<<" ";
        x=(x*i)/__gcd(x,i);
    }
    cout<<x<<endl;

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

coming soon...

coming soon...

First of all the binary search solution is wrong see this sample:

4 5

1 1 1 5

$$$d = 3$$$ is better than 4. That happens because the time you do a refill matters.

Bruteforce on $$$d$$$ and let $$$i$$$ be the current customer index we are serving.

Know we are serving the $$$i_{th}$$$ customer we want to know after selling the $$$m-d + 1$$$ pice of pizza what customer we are serving?.

In other words we want to know how many customers we can fully serve with $$$m-d + 1$$$ pice starting at the $$$i_{th}$$$ cutomer.

Just do a binary search on the prefix sum array, to find how many customers you would fully serve,(there is a way in $$$O(1)$$$), name this operation as a "jump".

The Time complexity is the number of jumps times log, because of binary search or just the number of jumps in the $$$O(1)$$$ way.

For each $$$d$$$ we jump at most $$$\frac{S}{m-d + 1}$$$ times, where $$$S$$$ is the sum of array $$$a$$$.

Then the total number of jumps is less than $$$n.log(S)$$$, so the final time complexity is $$$O(n \cdot log(n) \cdot log(S))$$$ for the binary search solution and $$$O(n \cdot log(S))$$$ for the other soltuion without binary search.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int a[n + 1];
        vector<int>p{0};
        int s = 0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s += a[i];
            p.push_back(s);
        }
        int ans = m;
        for(int d=1;d<=m;d++){
            int cur = m;
            bool f = true;
            int i=1;
            while(i <= n){
                int j = upper_bound(p.begin(),p.end(),m - d + p[i-1]) - p.begin();
                if(j == n + 1){
                    break;
                }
                int s = p[j] - p[i-1];
                if(s > m){
                    f = false;
                }
                i = j + 1;
            }
            if(f){
                ans = d;
                break;
            }
        }
        cout<<ans<<'\n';
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int a[n + 1];
        int b[n + 1];
        int sm = 0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            b[i] = sm;
            sm += a[i];
        }
        int st[sm],en[sm];
        for(int i=1;i<=n;i++){
            int _en = b[i] + a[i];
            for(int j=b[i];j < _en;j++){
                st[j] = b[i];
                en[j] = _en;
            }
        }
        int ans = m;
        for(int d=1;d<=m;d++){
            int cur = m;
            bool f = true;
            int i = 0;
            while(i + m - d < sm){
                int j = en[i + m - d];
                if(j - i > m){
                    f = false;
                    break;
                }
                i = j;
            }
            if(f){
                ans = d;
                break;
            }
        }
        cout<<ans<<'\n';
    }
}

First of all let's solve the problem without question marks,that is considering the array to contain only 0 and 1.

If player $$$i$$$ can beat player $$$j$$$ put a directed edge from $$$i$$$ to $$$j$$$.

Then player $$$1$$$ could win if and only if it can reach every other player when doing a dfs or bfs traversal, and then you just print the order of visited edges in the dfs or bfs from last to first.

If there is a question mark that means $$$i$$$ can beat $$$j$$$ and $$$j$$$ can beat $$$i$$$, so just put tow edges one from $$$i$$$ to $$$j$$$ and the other from $$$j$$$ to $$$i$$$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 7;
int vis[N];
vector<int>g[N];
vector<pair<int,int>>vc;
void dfs(int u,int p){
    if(vis[u])
        return;
    vis[u] = 1;
    for(auto i:g[u]){
        dfs(i,u);
    }
    if(p >= 0){
        vc.push_back({p,u});
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            g[i].clear();
            vis[i] = 0;
        }
        string s[n];
        for(int i=0;i<n;i++){
            cin>>s[i];
            for(int j=0;j<n;j++){
                if(s[i][j] != '0'){
                    g[i].push_back(j);
                }
            }
        }
        vc.clear();
        dfs(0,-1);
        if(vc.size() == n - 1){
            cout<<"YeS\n";
            for(auto [a,b]:vc){
                cout<<a + 1<<" "<<b + 1<<'\n';
            }
            cout<<'\n';
        }else{
            cout<<"nO\n";
        }
    }
    return 0;
}
/*
*/

Consider the subgraph that contains all the black nodes.

Any path between two white nodes that are located inside that subgraph is not a clean white path.

Every other path is clean white.

First root the tree in a black node if there is no black node wait till the first query.

Then when comes a new query just keep going up with your uncolored parents and color them, that is joining them to the subgraph that contains the black nodes.

And keep updating the number of white nodes inside the subgraph.

Time complexity $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 7;
vector<int>g[N];
int f[N]; // parent
void dfs(int u,int p){
    for(auto i:g[u]){
        if(i == p)
            continue;
        f[i] = u;
        dfs(i,u);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,q;
        cin>>n>>q;
        for(int i=1;i<=n;i++){
            g[i].clear();
        }
        string st;
        cin>>st;
        int c[n + 1] = {};
        for(int i=0;i<n;i++){
            c[i + 1] = st[i] - '0';
        }
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int rt = 0;
        for(int i=1;i<=n;i++){
            if(!c[i]){
                rt = i;
                break;
            }
        }
        int vis[n + 1] = {};
        ll in = 0,out = n;
        if(rt){
            vis[rt] = 1;
            f[rt] = 0;
            dfs(rt,rt);
            out--;
        }
        for(int i=1;i<=n;i++){
            if(!c[i]){
                int u = i;
                while(!vis[u]){
                    out--;
                    if(c[u]){
                        in++;
                    }
                    vis[u] = 1;
                    u = f[u];
                }
            }
        }
        while(q--){
            int u;
            cin>>u;
            if(vis[u] && c[u]){
                in--;
            }
            if(!rt){
                rt = u;
                vis[rt] = 1;
                f[rt] = 0;
                dfs(rt,rt);
                out--;
            }
            c[u] = 0;
            while(!vis[u]){
                out--;
                if(c[u]){
                    in++;
                }
                vis[u] = 1;
                u = f[u];
            }
            cout<<in * out + out *  (out + 1) / 2<<'\n';
        }
    }

    return 0;
}
/*
00
*/

This problem is a free AC. Print Tourist or any thing in a single line

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<"Tourist";
}
/*

*/

coming soon...

coming soon...

Observation: you can't do a jump of size 2 forward more than one time. proof: when going from $$$i$$$ to $$$i+2$$$, you can't go from $$$i+2$$$ to $$$i+4$$$ because you will not be able to go back to visit $$$i+3$$$ and $$$i+1$$$ because if you did you will end at index $$$i+1$$$ not $$$n$$$.

Then if you want to do a jump of size 2 forward you have to go from i to i + 2 then go back to i + 1 then go forward to i + 3.

Just be greedy and compare $$$a_{i+1}$$$ with $$$a_{i+2}$$$ and go to the smaller one.

When tie, choose index $$$i+1$$$ it's better because after that you can choose between $$$i+2$$$ and $$$i+3$$$, but if you choose to go to $$$i+2$$$ you can't choose between $$$i+1$$$ and $$$i+3$$$ you will be forced to go to $$$i+1$$$ then $$$i+3$$$.

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        vector<int>b{a[0]};
        for(int i=1;i<n;i++){
            if(i + 2 < n && a[i + 1] < a[i]){
                b.push_back(a[i + 1]);
                b.push_back(a[i]);
                b.push_back(a[i + 2]);
                // i-1 i i+1 i+2
                i += 2;
            }else{
                b.push_back(a[i]);
            }
        }
        for(auto i:b){
            cout<<i<<" ";
        }
        cout<<'\n';
    }

    return 0;
}
/*
*/

Simulate the process in anyway you want.

Put a pointer in the begining of the array, that is just a variable $$$l$$$ with value equals to $$$1$$$ and another pointer $$$r$$$ with value equals to $$$n$$$ that indicates the end of the array.

That helps simulating the process and you increase $$$l$$$ in the even operations and decrease $$$r$$$ in odd operations.

If $$$k$$$ is odd then print elements from $$$l$$$ to $$$r$$$, otherwise print them from $$$r$$$ to $$$l$$$.

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

#include <bits/stdc++.h>
using namespace std;
#define GO cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
typedef long long ll;
int main()
{
    GO
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int l=0,r=n-1;
    for(int i=0;i<k;i++){
        if(i&1){
            r--;
        }else{
            l++;
        }
    }

    if(k%2 == 1){
        for(int i=r;i>=l;i--){
            cout<<v[i]<<" ";
        }
    }else{
        for(int i=l;i<=r;i++){
            cout<<v[i]<<" ";
        }
    }
    return 0;
}
/*
*/

We compute the total contribution over all prefixes of size $$$k$$$, for $$$k = 1$$$ to $$$n$$$:

Each prefix GCD can be written as:

Now, for each $$$d$$$, we find its contribution. If $$$d \mid a_i$$$, then $$$a_i = b_i \cdot d$$$, and since $$$a_i \leq m$$$, we get:

So, there are $$$\left\lfloor \frac{m}{d} \right\rfloor$$$ choices for each $$$b_i$$$, and the total number of such sequences of length $$$k$$$ is:

Therefore:

Now we swap the order of summation:

Let $$$x = \left\lfloor \frac{m}{d} \right\rfloor$$$, then:

Now factor out $$$m^n$$$:

Let:

If $$$d = 1$$$, then $$$x = m \Rightarrow \frac{x}{m} = 1 \Rightarrow s = n$$$

If $$$d \gt 1$$$, then $$$\frac{x}{m} \lt 1$$$, so it becomes a geometric series:

Thus, the final answer is:

Now note that $$$s$$$ has only $$$\sqrt{m}$$$ different values because $$$x = \left\lfloor \frac{m}{d} \right\rfloor$$$ has $$$\sqrt{m}$$$ different values.

Then we can compute the answer in $$$O(\sqrt{m})$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e6;
int p[N + 1],phi[N + 1];
ll s[N + 1];
void sieve(){
    for(int i=1;i<=N;i++){
        phi[i] = i;
    }
    p[1] = 1;
    s[0] = 0;
    s[1] = 1;
    for(int i=2;i<=N;i++){
        if(!p[i]){
            for(int j=i;j<=N;j+=i){
                phi[j] -= phi[j] / i;
                p[j] = 1;
            }
        }
        s[i] = s[i-1] + phi[i];
        s[i] %= mod;
    }
}
ll fast_pow(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1){
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll get(ll k,ll n){
    // k^0 + k^1 + ...+ k^n
    if(k == 1){
        return n + 1;
    }
    ll a = fast_pow(k,n + 1) + mod - 1;
    ll b = fast_pow(k-1,mod - 2);
    return a * b % mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sieve();
    int t;
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;

        ll ans = 0;
        ll im = fast_pow(m,mod - 2);
        for(int l = 1, r; l <= m; l = r + 1){
            r = m / (m / l);
            ll k = (ll)m / l * im % mod;
            ll c = (get(k,n) + mod - 1) % mod;
            ll ss = (s[r] - s[l-1] + mod) % mod;
            ans += c * ss % mod;
            ans %= mod;
        }
        ans = ans * fast_pow(m,n) % mod;
        cout<<ans<<'\n';
    }

    return 0;
}
/*
cont[j] = (phi(d) * (M/d)^j) * M^(N-j)
*/

Doing $$$and$$$ operation before $$$or$$$ operation is always better than doing $$$or$$$ then $$$and$$$.

consider each bit and write its values in an array you can see that for this array of zeros and ones its always better to do $$$and$$$ then $$$or$$$.

That is for each bit the optimal is to do $$$or$$$ operation for the last $$$n-x$$$ elements.

So that is the optimal for our original problem.

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

int main()
{
    GO
    int t;
    cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;        
        int ans = 0;
        int a[n];
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = x; i < n; i++) ans |= a[i];
        cout << ans << '\n';
    }
    return 0;
}

Consider each bit,there are 3 types of bits:

• The bit of type1: its value is $$$0$$$ in the entire array
• The bit of type2: its value is $$$1$$$ in the entire array
• The bit of type3: it has at least one $$$0$$$ value in the array and at least one $$$1$$$ value in the array

Consider the trival cases:

• The case of $$$0$$$ happens when the entire array is already equal
• The case of $$$-1$$$ happens only when some bit of type3 is $$$off$$$ in $$$x$$$
• The case of $$$ceil(\frac{n}{m})$$$ happens when you have to do the operation to every element in the array, happens when there is a bit of type1 that is $$$on$$$ in $$$x$$$

Now after processing the trival cases we have: every bit of type3 $$$on$$$ in $$$x$$$ and every bit of type1 is $$$off$$$ in $$$x$$$.

bits of type2 are totally unnecessary you can just ignore them and delete them from $$$x$$$ and from array $$$a$$$

Then $$$x$$$ now has only one value (considering we have had prcessed the trival cases), solve the problem for that value before the queries.

Solving the subtask when $$$x$$$ is fixed: after doing the operation the final value of each element will be $$$goal$$$ = $$$x | a_1$$$, you need to change the value of the element $$$i$$$ if its not equal to $$$goal$$$, you can use $$$dp$$$.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int a[n + 1];
        bool f = true;
        int ad = (1<<30) - 1,oor = 0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i] != a[1])
                f = false;
            oor |= a[i];
            ad &= a[i];
        }
        int xr = (oor ^ ad);
        int dp[n + 1];
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            if(a[i] == oor){
                dp[i] = dp[i-1];
            }else{
                dp[i] = dp[max(0,i-m)] + 1;
            }
        }
        int q;
        cin>>q;
        while(q--){
            int x;
            cin>>x;
            if(f){
                cout<<"0\n";
                continue;
            }
            if((x & xr) != xr){
                cout<<"-1\n";
                continue;
            }
            if((x & oor) != x){
                cout<<(n + m - 1) / m<<'\n';
                continue;
            }
            cout<<dp[n]<<'\n';
        }
    }
}
/*

*/

There are many solutions to this problem, I will discuss mine.

consider three cases $$$n$$$ is a power of 2, $$$n - 1$$$ is a power of 2, the otherwise case.

The first two cases are trival:

When $$$n$$$ is a power of $$$2$$$:

print: $$$(1, n, 2, 3, 4, ... ,n-1)$$$

When $$$n - 1$$$ is a power of $$$2$$$:

print: $$$(1, n, n-1, 2, 3, ..., n-2)$$$

The Third case:

The Main idea of my solution is that when you turn the smallest bit that is $$$on$$$ in a number $$$n$$$ to $$$off$$$, the $$$or$$$ of any two elements in the range from $$$(n - 2^i)$$$ to $$$n-1$$$ is less than $$$n$$$ where $$$i$$$ is the smallest bit. note that the $$$n$$$ $$$or$$$ $$$(n-2^i)$$$ is equal to $$$n$$$.

Then this arrangment is helpfull and has a maxumum or of adjecnet of $$$n$$$ (not considering the cyclic pair):

.

The entire solution:

Using the Main idea i discussed we always can make the maximum equals to $$$n$$$.

Let's start the array with $$$n$$$ then iterate over the $$$on$$$ bits of $$$n$$$ form the smaller to the greater.

consider the smaller bit let it be $$$i$$$, if we make this bit $$$off$$$ we can make any combination fo the smaller $$$off$$$ bits as $$$on$$$ and put them aside to each other that is printing the range from $$$(x - 2^i)$$$ to $$$x - 1$$$

Now make that bit $$$off$$$ for the rest of the time.

Now when going to the next bit, we can do the same. make this bit $$$off$$$ (all the previous bits also are $$$off$$$) then you can make any combination of the smaller bits $$$on$$$ and put them aside to each other.

But the array is cyclic, that is the last element must be submask of $$$n$$$, you can take any power of 2 that is a submask of $$$n$$$ and put it.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define log(x) (31 ^ __builtin_clz(x))
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(n == 1){
            cout<<"1\n";
            continue;
        }
        if(n == 2){
            cout<<"1 2\n";
            continue;
        }
        int lg = log(n);
        if(n == (1<<lg) ){
            cout<<"1 ";
            cout<<n<<" ";
            cout<<"2 ";
            for(int i=3;i<n;i++){
                cout<<i<<" ";
            }
            cout<<endl;
        }else if(n == (1<<lg) + 1){
            cout<<"1 ";
            cout<<n<<" ";
            cout<<n - 1<<" ";
            for(int i=2;i<n-1;i++){
                cout<<i<<" ";
            }
            cout<<endl;
        }else{
            for(int i=0;i<20;i++){
                if( n >> i & 1){
                    lg = i;
                    break;
                }
            }
            cout<<(1<<lg)<<" ";
            cout<<n<<" ";
            for(int i=0;i<20;i++){
                if(n >> i & 1){
                    for(int j = (n ^ (1 << i));j < n;j++){
                        if(j == (1 <<lg) || j == 0)
                            continue;
                        cout<<j<<" ";
                    }
                    n ^= (1 << i);
                }
            }
            cout<<endl;
        }
    }
}
/*
11001100
11001000
11001001
11001010
11001011
11000000
11000001
...
11000111
10000000
10000001
...
10111111
00000001
...
01111111


1000
0001
0011
0100
0101
0110
0111
0010

1001
1000
0001
0010
0011
0100
0101
0111

1010
1000
1001
0001
..
0111
*/