Problem Description

Since the constraints are small, you only need to simulate this process.

You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:

• 1 damage if the i-th attack is not divisible by 3.
• 2 damage if the i-th attack is divisible by 3.

If your health will becomes less than $$$0$$$ when the dragon attack you (in other words, your hp is less than $$$k$$$) , you must use a bandage.

void solve(){
    int h,k,n;cin>>h>>k>>n;
    int ans = 0, l = k, r = 1;
    while(h > 1){
        r++;
        k -= n;
        if(k <= 0){
            k = l - n;
            ans++;
        }
        if(r % 3 == 0){
            h-=2;
        }else{
            h--;
        }
    }
    cout<<ans<<endl;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Problem Statement

OwlBear is attacking a village. The village has n cannons, each dealing a_i damage. At the k-th second, the OwlBear is protected from the cannon at index (*k*-1) mod n. Given q queries, each with a damage threshold h, find the minimum number of seconds required to deal at least h damage.

Analysis

The key idea is to precompute the prefix sums of the damage dealt in each second, excluding the blocked cannon. Let sum be the total damage all cannons can deal in one second. Then, the damage dealt in the i-th second is sum - a[i % n]. We can create a prefix sum array p where p[i] stores the total damage dealt from second 1 to second i.

To answer a query with damage h, we can first calculate how many full cycles of n seconds are needed. This can be done by ans = h / p[n-1]. The remaining damage is h -= (ans * p[n-1]). Then, we multiply ans by n to get the number of seconds in full cycles. If there is still remaining damage (h > 0), we use binary search (specifically lower_bound) on the prefix sum array p to find the minimum number of additional seconds needed.

Solution

1. Read n and the damage array a.
2. Calculate the total damage sum and create the prefix sum array p where p[i] = sum - a[i] and accumulate the prefix sums.
3. For each query h:
   • Calculate the number of full cycles: ans = h / p[n-1].
   • Update the remaining damage: h -= (ans * p[n-1]).
   • Multiply ans by n.
   • If h > 0, use lower_bound on p to find the index of the first value greater than or equal to h. Add this index + 1 to ans to get the final answer.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<ll> a(n), p(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        ll sum = 0;
        for (int i = 0; i < n; i++) sum += a[i];
        for (int i = 0; i < n; i++) p[i] = sum - a[i];
        for (int i = 1; i < n; i++) p[i] += p[i - 1];
        int q;
        cin >> q;
        while (q--) {
            ll h;
            cin >> h;
            ll ans = h / p[n - 1];
            h -= (ans * p[n - 1]);
            ans *= n;
            if (h) ans += lower_bound(p.begin(), p.end(), h) - p.begin()+1;
            cout << ans << '\n';
        }
    }
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

We can set $$$a_{i,j} = a_{j,i} = i + j$$$ for $$$i \neq j$$$, and set $$$a_{i,i} = 2$$$ for all $$$1 \le i \le n$$$.

Now, if $$$n$$$ is even, all conditions are met.

If $$$n$$$ is odd, the XOR of all elements is $$$2$$$. To balance out that $$$2$$$, we can add $$$2$$$ to $$$a_{3,1}$$$.

We set $$$a_{i,j}$$$ as the minimum prime factor of (i+j).

Now, if $$$n$$$ is even, all conditions are met.

If $$$n$$$ is odd, the XOR of all elements is $$$2$$$. There are $$$2$$$ cases:

• $$$n \le 17$$$. In this case we change $$$a_{1,1}$$$ to $$$4$$$ and $$$a_{2,2}$$$ to $$$6$$$.

• $$$n > 17$$$. In this case we change $$$a_{17,18}$$$ from $$$5$$$ to $$$7$$$.

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

int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int t;
	cin>>t;

	while(t--){

		int n;
		cin>>n;

		vector<vector<int>> a(n+1,vector<int>(n+1,0));

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) a[i][j] = 2;
				else a[i][j] = i+j;
			}
		}

		if(n&1){
			a[3][1] = 6;
		}

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) cout << a[i][j] << ' ';
			cout << endl;
		}

	}
	
	return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define mod  1000000007
#define mod2 998244353
#define ll long long
#define bl __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"
using Mat = array<array<ll,2>,2>;
 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")
 
ll power(ll x,ll y,ll z=LLONG_MAX){
	ll res=1;
	while(y>0){
		if(y%2) res=(res*x)%z;
		y/=2;
		if(y) x=(x*x)%z;
	}return res%z;
}
 
ll gcd(ll a,ll b,ll& x,ll& y){
	x=1,y=0;
	ll x1=0,y1=1,a1=a,b1=b;
	while(b1){
		ll q=a1/b1;
		tie(x,x1)=make_tuple(x1,x-q*x1);
		tie(y,y1)=make_tuple(y1,y-q*y1);
		tie(a1,b1)=make_tuple(b1,a1-q*b1);
	}return a1;
}
 
#define MX 1e4
vector<ll> spf(MX+2,1);
vector<ll> gpf(MX+2,0);
void sieve(){
	spf[0]=0;
	for(ll i=2;i<3;i++){
		if(spf[i]==1){
			for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
		}
	}for(ll i=3;i<MX+1;i+=2){
		if(spf[i]==1){
			for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
		}
	}for(ll i=2;i<=MX;i++) if(gpf[i]==0) for(ll j=i;j<=MX;j+=i) gpf[j]=i;
	return; 
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
	sieve(); // for SPF
	cin>>t;
	ll tt=t;
	string s,s2;
	while(tt--){
		cin>>n;
		assert(n!=1ll);
		vector<vector<ll>> a(n+1ll,vector<ll>(n+1ll,0ll));
		f(i,n) f(j,n) a[i+1][j+1] = spf[i+j+2ll];
		if(n%2ll == 1ll){
			if(n>18){
				a[17][18] = 7;
			}
			else{
				a[2][2] = 4ll;
				a[3][3] = 6ll;
			}
		}
		f(i,n){
			f(j,n) cout<<a[i+1][j+1]<<' ';
			cout<<'\n';
		}
	}
	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

There are only $$$n$$$ possible different shifts.Let's calculate cost for each of them in O(1).

Assume one-based indexing for array.
Let cost[i] represent the cost of the array after i shifts.

Initial cost:
cost[0] = 1*a1 + 2*a2 + ... + n*an

cost after first shift:

Rewriting cost[1] in terms of cost[0]

cost after second shift:

Rewriting cost[2] in terms of cost[1]

The generalized formula cost[i] from cost[i-1] terms :

Why the generalized formula is correct?

Using this formula, we can compute the cost for all shifts in O(1) per shift and take minimum among all, resulting in an overall complexity of O(n).

Let's take

$$$ cost_0 = 1 * a_1 + 2 * a_2 + ... + n * a_n $$$

$$$ sum = a_1 + a_2 + ... + a_n $$$

for now let's assume no updates on array ( i.e NO query 1 ( static array ) ). In easy version, we know for i>=1

$$$ cost_i = cost_{i-1} - sum + n * a_i $$$

$$$cost_i$$$ in terms of $$$cost_{i-2}$$$ :

If we continue this, we can express the cost at the i-th shift in terms of the 0-th shift:

Now, if there are updates in the array, the formula for the cost is modified. When an update occurs at inddex $$$ind$$$ , we modify the initial cost as follows:

let's say,

prev = $$$a_{ind}$$$ before update

curr = $$$a_{ind}$$$ after update

we modify the initial cost as follows:

The sum also changes:

To efficiently manage the updates and calculate the prefix sum, we can use Fenwick tree or segment tree (You can learn more about it https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/ ).

Thus, the final formula after k shifts, considering updates, is:

Time Complexity: $$$ O((n+q)*logn) $$$

Space Complexity:$$$ O(n+q) $$$

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    long long t;
    cin>>t;
 
    while(t--)
    {
        long long n;
        cin>>n;
        long long a[n];
        long long sum=0;
        long long ans=0;
        for(long long i=0;i<n;i++)
        {
            cin>>a[i];
            sum+=a[i];
            ans+=((i+1)*a[i]);
        }
 
        long long cost=ans;
        for(long long i=0;i<n;i++) 
        {
            cost=cost-sum+n*a[i];
            ans=min(ans,cost);
        }
        cout<<ans<<"\n";
    }
 
    return 0;
}

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

long long BIT[200000]={0}, a[200000]={0}, n;
void update(long long x, long long delta)
{
      for(; x <= n; x += x&-x)
        BIT[x] += delta;
}
long long query(long long x)
{
     long long sum = 0;
     for(; x > 0; x -= x&-x)
        sum += BIT[x];
     return sum;
}

int main() {

    long long t;
    cin>>t;
    while(t--) 
    {
        cin>>n;
        long long cost=0;
        long long sum=0;
        for(long long i=0;i<n;i++)
        {
            cin>>a[i];
            update(i+1,a[i]);
            cost+=((i+1)*a[i]);
            sum+=a[i];
        }

        long long q;
        cin>>q;

        while(q--)
        {
            long long ty;
            cin>>ty;
            if(ty==1)
            {
                long long ind,x;
                cin>>ind>>x;
                cost-=((ind)*(a[ind-1]));
                sum+=(x-a[ind-1]);
                update(ind,x-a[ind-1]);
                a[ind-1]=x;
                cost+=((ind)*(a[ind-1]));
            }
            else
            {
                long long k;
                cin>>k;
                k%=n;
                cout<<cost-(k)*(sum)+n*(query(k))<<"\n";
            }
        }

        for(int i = 0; i < n; i++) update(i + 1, -a[i]);
    }

    return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define mod  1000000007
#define mod2 998244353
#define ll long long
#define bl __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"
using Mat = array<array<ll,2>,2>;
 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")
 
ll power(ll x,ll y,ll z=LLONG_MAX){
    ll res=1;
    while(y>0){
        if(y%2) res=(res*x)%z;
        y/=2;
        if(y) x=(x*x)%z;
    }return res%z;
}
 
ll gcd(ll a,ll b,ll& x,ll& y){
    x=1,y=0;
    ll x1=0,y1=1,a1=a,b1=b;
    while(b1){
        ll q=a1/b1;
        tie(x,x1)=make_tuple(x1,x-q*x1);
        tie(y,y1)=make_tuple(y1,y-q*y1);
        tie(a1,b1)=make_tuple(b1,a1-q*b1);
    }return a1;
}
 
template<class T, class U>
// T -> node, U->update.
struct Lsegtree{
    vector<T>st;
    vector<U>lazy;
    ll n;
    T identity_element; // related to query
    U identity_update;  // related to update
    Lsegtree(ll n, T identity_element, U identity_update)
    {
        this->n = n;
        this->identity_element = identity_element;
        this->identity_update = identity_update;
        st.assign(4*n,identity_element);
        lazy.assign(4*n, identity_update);
    }
    T combine(T l, T r)
    {
        // change this function as required.
        // related to query
        T ans = l + r;
        return ans;
    }
    void buildUtil(ll v, ll tl, ll tr, vector<T>&a)
    {
        if(tl == tr)
        {
            st[v]=a[tl];
            return;
        }
        ll tm = (tl + tr)/2;
        buildUtil(2*v + 1, tl, tm,a);
        buildUtil(2*v + 2,tm+1,tr,a);
        st[v] = combine(st[2*v + 1], st[2*v + 2]);
    }
    // change the following 2 functions, and you're more or less done.
    T apply(T curr, U upd, ll tl, ll tr)
    {   
        // related to update and query
        T ans = (upd)*(tr-tl+1);
        return ans;
    }
    U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)
    {   
        // related to update
        U ans = old_upd;
        ans=(new_upd);
        return ans;
    }  
    void push_down(ll v, ll tl, ll tr)
    {
        if(lazy[v] == identity_update)return;
        st[v] = apply(st[v], lazy[v], tl, tr);
        if(2*v + 2 < 4*n)
        {
            ll tm = (tl + tr)>>1;
            lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);
            lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr);            
        }
        lazy[v] = identity_update;
    }
    T queryUtil(ll v, ll tl, ll tr, ll l, ll r)
    {
        push_down(v,tl,tr);
        if(l > r)return identity_element;
        if(tr < l or tl > r)
        {
            return identity_element;
        }
        if(l <= tl and r >= tr)
        {
            return st[v];
        }
        ll tm = (tl + tr)>>1;
        return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));
    }
    void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)
    {
        push_down(v,tl,tr); 
        if(tr < l or tl > r)return;
        if(tl >=l and tr <=r)
        {
            lazy[v] = combineUpdate(lazy[v],upd,tl,tr);
            push_down(v,tl,tr);
        }
        else
        {
            ll tm = (tl + tr)/2;
            updateUtil(2*v+1,tl,tm,l,r,upd);
            updateUtil(2*v+2,tm+1,tr,l,r,upd);
            st[v] = combine(st[2*v + 1], st[2*v+2]);
        }
    }
    void build(vector<T>a)
    {
        assert(a.size() == n);
        buildUtil(0,0,n-1,a);
    }
    T query(ll l, ll r)
    {
        return queryUtil(0,0,n-1,l,r);
    }
    void update(ll l,ll r, U upd)
    {
        updateUtil(0,0,n-1,l,r,upd);
    }
    ll find_ind(ll v,ll tl,ll tr,ll x){
        // have to store maximums for this to work
        if(st[v]>x) return 0;
        if(tl==tr) return tl;
        ll tm=(tl+tr)/2;
        if(st[v+v+1]<=x) return find_ind(v+v+1,tl,tm,x);
        else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]);
    }
};
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
    // sieve(); // for SPF
    cin>>t;
    ll tt=t;
    string s,s2;
    while(tt--){
        ll n;
        cin>>n;
        inp(a,n);
        ll sum = accumulate(all(a),0ll);
        ll val = 0ll;
        f(i,n) val += ((i+1)*a[i]);
        Lsegtree<ll,ll> sega(n,0ll,LLONG_MIN);
        sega.build(a);
 
        ll q;
        cin>>q; 
        while(q--){
            ll x;
            cin>>x;
            if(x==1ll){
                ll ind,p;
                cin>>ind>>p;
                ind--;
                sega.update(ind,ind,p);
                sum += (p-a[ind]);
                val += ((ind+1)*(p-a[ind]));
                a[ind] = p;
            }
            else{
                ll k;
                cin>>k;
                k %= n;
                ll ans = val;
                if(k>0ll){
                    ans += (n*sega.query(0ll,k-1ll));
                    ans -= (k*sum);
                }
                cout<<ans<<'\n';
            }
        }
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Solution 1:

This algorithm is a randomized algorithm.

We randomly select two fixed points $$$x$$$ and $$$y$$$, then for all $$$z \neq x, y$$$, query "? $$$x$$$ $$$y$$$ $$$z$$$". If the result is 0, it means $$$z$$$ and $$$x$$$ are on the same side of $$$y$$$; otherwise, $$$z$$$ and $$$x$$$ are on different sides of $$$y$$$.

Thus, we use $$$y$$$ as the pivot and partition the elements into the left and right halves. To determine which side is the actual left half, we need to perform type $$$1$$$ operation once, (this is only required in the first partitioning step. After determining the correct position of $$$y$$$, no more operations of this type are needed).

Once we know the correct position of $$$y$$$, we can recursively solve the left and right halves.

You might have already noticed that this is essentially the process of quick sort. Therefore, the complexity proof is identical to that of quicksort.

Solution 2:

This algorithm is a deterministic algorithm.

If we can determine the value of $$$p[1]$$$, then we can perform a comparison "? $$$p[1]$$$ $$$x$$$ $$$y$$$", where we compare two numbers.

The method to determine $$$p[1]$$$ is given by the following code:

int u = 1, v = 2;
for (int i = 3; i <= n; i++) {
    int res = ask(u, i, v);
    if (!res) {
        res = ask(u, v, i);
        if (res) v = i;
        else u = i;
    }
}
cout << "1 " << u << ' ' << v << endl;
int res;
cin >> res;
if (!res) swap(u, v);

After determining $$$p[1]$$$, you can solve the problem using any $$$O(n \log n)$$$ sorting algorithm.

#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>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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,n,keypos;
int p[N];
/*
 // 创建随机数生成器
std::random_device rd; // 获得随机种子
std::mt19937 g(rd());  // 使用Mersenne Twister引擎
*/

void init()
{
    srand(time(0));
    cin>>n;
    keypos=0;
}

int ask1(int x,int y)
{
    int t;
    cout<<"1 "<<x<<" "<<y<<"\n";
    cout.flush();
    cin>>t;
    return t;
}

int ask2(int x,int y,int z)
{
    int t;
    cout<<"2 "<<x<<" "<<y<<" "<<z<<"\n";
    cout.flush();
    cin>>t;
    return t;
}

void work(int L,int R,vector<int> &v)
{
    if(L>R) return ;
    if(L==R)
    {
        p[L]=v[0];
        return ;
    }
    if(L==R-1)
    {
        if(R<keypos)
        {
            if(!ask2(v[0],v[1],p[keypos])) swap(v[0],v[1]);
        }
        else
        {
            if(!ask2(v[1],v[0],p[keypos])) swap(v[0],v[1]);
        }
        p[L]=v[0];
        p[R]=v[1];
        return ;
    }
    // 使用std::shuffle打乱vector
    int midpos;
    vector<int> lhalf,rhalf;

    //shuffle(v.begin(), v.end(), g);
    random_shuffle(v.begin(), v.end());
    lhalf.push_back(v[0]);
    /*
    cout<<"L="<<L<<" R="<<R<<"\n shuffled v[]=";
    for(int i=0;i<v.size();i++) cout<<v[i]<<' ';
    cout<<"\n";
    //
    //
    cout<<"lhalf[]=";
    for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';
    cout<<"\n";
    */
    for(int i=2;i<v.size();i++)
    {
        if(ask2(v[0],v[1],v[i])) rhalf.push_back(v[i]);
        else lhalf.push_back(v[i]);

        /*
        cout<<"lhalf[]=";
        for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';
        cout<<"\n";
        */
    }
    if(!keypos)
    {
        if(!ask1(v[0],v[1])) swap(lhalf,rhalf);
        midpos=lhalf.size()+1;
        p[midpos]=v[1];
        keypos=midpos;
        //
        //printf("keypos=%d\n",keypos);
        //
    }
    else
    {
        if(R<keypos)
        {
            if(!ask2(v[0],v[1],p[keypos])) swap(lhalf,rhalf);
        }
        else
        {
            if(!ask2(v[1],v[0],p[keypos])) swap(lhalf,rhalf);
        }
        midpos=lhalf.size()+L;
        p[midpos]=v[1];
    }
    /*
    cout<<"lhalf[]=";
    for(int i=0;i<lhalf.size();i++) cout<<lhalf[i]<<' ';
    cout<<"\n";
    cout<<"rhalf[]=";
    for(int i=0;i<rhalf.size();i++) cout<<rhalf[i]<<' ';
    cout<<"\n";
    */
    work(L,midpos-1,lhalf);
    work(midpos+1,R,rhalf);
}

void solve()
{
    vector<int> v;
    for(int i=1;i<=n;i++) v.push_back(i);
    work(1,n,v);
    cout<<"! ";
    for(int i=1;i<=n;i++) cout<<p[i]<<(i==n?'\n':' ');
    cout.flush();
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

int main()
{
    //fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

// Problem: G. Interactive is Fun
// Contest: Codeforces - TheForces Round #39 (DIV4-Forces)
// URL: https://codeforces.net/gym/105651/problem/G
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<int> p(n + 1);
	for (int i = 1; i <= n; i++) p[i] = i;
	auto ask = [&](int x, int y, int z) -> bool {
		cout << "2 " << x << ' ' << y << ' ' << z << endl;
		int res; cin >> res;
		return res;
	};
	int u = 1, v = 2;
	for (int i = 3; i <= n; i++) {
		int res = ask(u, i, v);
		if (!res) {
			res = ask(u, v, i);
			if (res) v = i;
			else u = i;
		}
	}
	cout << "1 " << u << ' ' << v << endl;
	int res; cin >> res;
	if (!res) swap(u, v);
	stable_sort(p.begin() + 1, p.end(), [&](int i, int j) {
		return ask(u, i, j);
	});
	cout << "! ";
	for (int i = 1; i <= n; i++) cout << p[i] << " ";
	cout << endl;
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

Amazing problem: Good problem: Average problem: Bad problem: Didn't solve:

Note that performing an operation is always optimal as it won't decrease the answer.

At first, lets find the number of good subarrays before applying the operation. For this, the condition is $$$a_l + a_{l+1} ... + a_r >= k*(r-l+1)$$$ which is $$$pre[r] - k*r >= pre[l-1] - k*(l-1)$$$. So we can make a new array $$$b$$$ where $$$b_i = pre[i] - k*i$$$ and the initial number of good subarrays is equal to the number of inversions in the array $$$b$$$.

Now, lets say we increment $$$a_i$$$ by $$$1$$$ for some $$$i$$$, then the additional good subarrays formed should have their left boundary to the left of $$$i$$$ or equal to $$$i$$$ and their right boundary to the right of $$$i$$$ or equal to $$$i$$$ $$$(i.e., l \le i \le r)$$$ and $$$b_r = b_{l-1} - 1$$$. If we have the number of additional good subarrays when the operation is performed at $$$i^{th}$$$ position, we can easily find the number of additional good subarrays when the operation is performed at $$$(i+1)^{th}$$$ position using a map.

Finally we take maximum over all positions and add it to the initial answer.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        ll n, k;
        cin >> n >> k;

        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<ll> b(n + 1, 0ll);
        for (int i = 0; i < n; i++) {
            b[i + 1] = b[i] + (a[i] - k);
        }

        ll ans = 0;

        oms<ll> inv;
        inv.insert(0);

        for (int i = 0; i < n; i++) {
            ans += inv.order_of_key(b[i + 1] + 1);
            inv.insert(b[i + 1]);
        }

        ll mx = 0;
        map<ll, ll> left, right;

        for (int i = 0; i < n; i++) {
            right[b[i + 1]]++;
        }

        left[0]++;
        ll val = 0;

        for (int i = 0; i < n; i++) {
            if (b[i + 1] == -1) {
                val++;
            }
        }

        mx = val;

        for (int i = 2; i <= n; i++) {
            val += right[b[i - 1] - 1];
            val -= left[b[i - 1] + 1];

            left[b[i - 1]]++;
            right[b[i - 1]]--;

            mx = max(mx, val);
        }

        ans += mx;
        cout << ans << '\n';
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve: