Codeworks round 723 (Div. 2)

This is a very awesome ,construct There are a lot of questions

A

#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
int a[maxn];
int b[maxn];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=2*n;i++)scanf("%d",&a[i]);
        sort(a+1,a+2*n+1);
        for(int i=1;i<=n;i++)
        b[2*i-1]=a[i],b[2*i]=a[i+n];
        for(int i=1;i<=2*n;i++)printf("%d ",b[i]);
        puts("");
    }
}

B

Melo chicken theory

If n and m Coprime , So for n and m In a set of calculations consisting only of additions , The biggest thing that doesn't contain elements is n*m-n-m

#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
int a[maxn];
int b[maxn];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        // vector<int> num;
        int x;
        scanf("%d",&x);
        bool flag=false;
        if(x>1099) flag=true;
        else
        {
            for(int i=0;i<11&&x>=0;i++)
            {
                
                if(x%11==0)
                {
                    flag=true;
                    break;
                }
                x-=111;
            }
        }
        // cout<<x<<endl;
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
}

C2

Priority queue

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n;ll sum=0;
    scanf("%d",&n);
    priority_queue<int,vector<int>,greater<int>> heap;
    int cnt=0;
    heap.push(0);
   while(n--)
   {
       int x;
       scanf("%d",&x);
       if(sum+x<0)
       {
           if(heap.top()<x)
           {
               sum-=heap.top();
               heap.pop();heap.push(x);
               sum+=x;
           }
       }
       else {sum+=x;heap.push(x);cnt++;}
   }
   cout<<cnt<<endl;
}

D

Considering that merging the same letters will increase the complexity .

So we can boldly guess that the optimal solution must be a bunch of shapes such as xxxxxyyyyyy.... Things like that x by ANTO A certain letter in ,y For one of the three remaining

It can be easily proved by the method of counter evidence , The next one is 4! Enumeration

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
char s[maxn];
char op[5]="ANOT";
map<char,int> mp={
   {'A',0},{'N',1},{'O',2},{'T',3}};
int cnt[4],a[maxn];
int cal[4][4];
int mx;
signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        mx=0;
        memset(cnt,0,sizeof(cnt));
        memset(cal,0,sizeof(cal));
        scanf("%s",s+1);
        int n=strlen(s+1);
        for(int i=1;i<=n;i++)a[i]=mp[s[i]],cnt[mp[s[i]]]++;
        for(int temp,c=0;temp=0,c<4;c++) for(int i=1;i<=n;i++)
        {
            cal[c][a[i]]+=temp;
            if(a[i]==c)temp++;
        }
        vector<int> permutation={0,1,2,3},ans=permutation;
        do
        {
          int res=0;
          for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)res+=cal[permutation[j]][permutation[i]];
          if(res>mx)mx=res,ans=permutation;
        }while(next_permutation(permutation.begin(),permutation.end()));
        for(auto t:ans)
        while(cnt[t]--)printf("%c",op[t]);
        puts("");
    }
}

E

Almost by the sa Array dissuasion

hold sa The array is converted to rk Array

You will find that in fact, it is similar to

k>=x1>x2>=x3>=x4>x5

in x1,x2,x3,x4,x5 All possible values

convert to x5<x4<x3+1<x2+2<x1+2<=k+3 All the possibilities of , among 3 Is equal sign quantity .

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+10;
const int p=998244353;
typedef long long ll;
// char s[maxn];
int n,k;
int sa[maxn],rk[maxn];
int fact[maxn],infact[maxn];
void init()
{
    infact[1]=1;
    for(int i=2;i<maxn;i++)
        infact[i]=((-(ll)(p/i)*infact[p%i]%p+p)%p);
}
int main()
{
    scanf("%d%d",&n,&k);
    rk[sa[n+1]=0]=n+1;
    for(int i=1;i<=n;i++)scanf("%d",&sa[i]),rk[++sa[i]]=i;
    init();
    int m=0;
    for(int i=1;i<n;i++)
    m+=rk[sa[i]+1]<rk[sa[i+1]+1];
    ll res=1;
    for(int i=m+k;i>m+k-n;i--)res=res*i%p;
    for(int i=2;i<=n;i++)res=res*infact[i]%p;
    cout<<res<<endl;
}

F

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int p[maxn];
int w[maxn];
int query(int a,int b,int c)
{
    int x;
    printf("? %d %d %d\n",a,b,c);
    fflush(stdout);
    scanf("%d",&x);
    return x;
}
int n;
int a,b;
void init()
{
    for(int i=1;i<=13;i++)
        for(int j=i+1;j<=13;j++)
        for(int k=j+1;k<=13;k++)
        {
            if(query(i,j,k)*6<=n-4)
            {
                a=i;b=j;
                return ;
            }
        }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        init();
        vector<int> v;
        v.clear();
        int mx=0,id;
        // memset(w,0,sizeof(w));
        for(int i=1;i<=n;i++)
        {
            w[i]=0;
            if(i==a||i==b)continue;
            w[i]=query(a,b,i);
            if(w[i]>mx)
            {
                id=i;
                mx=w[i];
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(w[i]==mx-1)
            {
                v.push_back(i);
            }
        }
        if(v.size()==1)
        {
            a=id,b=v[0];
        }
        else 
        {
            int x=query(a,id,v[0]),y=query(a,id,v[1]);
            if(x<y)b=v[0];
            else b=v[1];
            a=id;
        }
        p[a]=1,p[b]=2;
        for(int i=1;i<=n;i++)
        {
            if(i==a||i==b)continue;
            p[i]=query(i,a,b)+2;
            
        }
        if(p[1]>p[2])
        for(int i=1;i<=n;i++)p[i]=n-p[i]+1;
        printf("! ");
        for(int i=1;i<=n;i++)printf("%d ",p[i]);
        // puts("");
        // printf("\n");
        // getchar();
        cout<<endl;
        scanf("%d",&n);
    }
}