oj.uz

Submission #713232

# Submission time Handle Problem Language Result Execution time Memory
713232 2023-03-21T10:55:23 Z Pacybwoah Diversity (CEOI21_diversity) C++14
0 / 100
 2 ms 2644 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

int main(){
    ll n,q;
    cin>>n>>q;
    if(q!=1) return 0;
    int a,b;
    vector<ll> vec(n);
    for(int i=0;i<n;i++) cin>>vec[i];
    cin>>a>>b;
    vector<ll> cnt(300001);
    for(int i=0;i<n;i++) cnt[vec[i]]++;
    vector<ll> p;
    for(int i=0;i<=300000;i++){
        if(cnt[i]>0) p.push_back(cnt[i]);
    }
    sort(p.begin(),p.end());
    vector<ll> f;
    for(int i=0;i<p.size();i+=2){
        f.push_back(p[i]);
    }
    for(int i=(p.size()%2==0?p.size()-1:p.size()-2);i>=0;i-=2) f.push_back(p[i]);
    ll sum=0,len=f.size();
    vector<ll> pre1(len),pre2(len);
    for(int i=1;i<len;i++){
        pre1[i]=pre1[i-1]+f[i]*i;
        pre2[i]=pre2[i-1]+f[i];
    }
    for(ll i=0;i<len;i++){
        sum+=f[i]*(f[i]+1)/2;
        sum+=f[i]*(pre1[n-1]-pre1[i]-(i-1)*(pre2[n-1]-pre2[i]));
    }
    cout<<sum<<"\n";
}

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -