Submission #737951

#	Time	Username	Problem	Language	Result	Execution time	Memory
737951		guagua0407	Diversity (CEOI21_diversity)	C++17	64 / 100	90 ms	9588 KiB

diversity

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n,q;
    cin>>n>>q;
    ll a[n];
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    vector<ll> vec;
    ll cnt=1;
    ll cur=a[0];
    for(ll i=1;i<n;i++){
        if(a[i]==cur){
            cnt++;
        }
        else{
            vec.push_back(cnt);
            cnt=1;
            cur=a[i];
        }
    }
    vec.push_back(cnt);
    sort(vec.begin(),vec.end());
    vector<ll> vec2;
    for(int i=0;i<vec.size();i+=2){
        vec2.push_back(vec[i]);
    }
    for(int i=((vec.size()-1)%2==0?vec.size()-2:vec.size()-1);i>=1;i-=2){
        vec2.push_back(vec[i]);
    }
    ll ans=0;
    ll now=0;
    for(auto v:vec2){   
        ans+=(now+v)*(n-now);
        ans-=(v)*(v-1)/2;
        now+=v;
    }
    cout<<ans;
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<vec.size();i+=2){
      |                 ~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36