oj.uz

Submission #857993

# Submission time Handle Problem Language Result Execution time Memory
857993 2023-10-07T09:18:39 Z danikoynov Diversity (CEOI21_diversity) C++14
0 / 100
 1 ms 6492 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

int n, q, a[maxn], cnt[maxn], m, val[maxn], used[maxn];

    vector < ll > groups;
    ll ans;
ll bef[maxn], aft[maxn];
void check()
{
    ll tot = 0;
    /**for (int i = 0; i < m; i ++)
        cout << val[i] << " ";
    cout << endl;*/

    ll bf = 0;
    for (int i = 0; i < m; i ++)
    {
        bef[i] = bf;
        bf += groups[val[i]];
    }
    ll af = 0;
    for (int i = m - 1; i >= 0; i --)
    {
        aft[i] = af;
        af += groups[val[i]];
    }

        for (ll i = 0; i < m; i ++)
    {
        tot = tot + i * groups[val[i]] * (bef[i] - aft[i]);
    }
    /**for (int i = 0; i < m; i ++)
        cout << groups[val[i]] << " ";
    cout << endl;
    cout << tot << endl;
    cout << "-----------" << endl;*/
    ll sf = 0;
    for (int i = 0; i < m; i ++)
    {
        ll cur = groups[i];
        tot = tot + cur * (cur + 1) / 2;
        tot = tot + groups[i] * sf;
        sf += groups[i];
    }
    ans = min(ans, tot);
}

void perm(int pos)
{
    if (pos == m)
        check();
    else
    {
        for (int i = 0; i < m; i ++)
        {
            if (!used[i])
            {
                val[pos] = i;
                used[i] = 1;
                perm(pos + 1);
                used[i] = 0;
                val[pos] = 0;
            }
        }
    }
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    int l, r;
    cin >> l >> r;

    for (int i = 1; i <= n; i ++)
        cnt[a[i]] ++;


    for (int i = 1; i <= n; i ++)
        if (cnt[i] > 0)
        groups.push_back((ll)(cnt[i]));

        ans = 1e18;
    m = groups.size();
    for (int j = 0; j < m; j ++)
    {
        int pos = 0;
        for (int d = j; d < m; d ++)
        {
            val[pos] = d;
            pos ++;
        }
        for (int d = j - 1; d >= 0; d --)
        {
            val[pos] = d;
            pos ++;
        }
        check();
    }
    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}
/**
4 1
1 1 1 1
1 2
2 4

4 1
2 1 3 2
1 4

*/

Compilation message

diversity.cpp: In function 'void solve()':
diversity.cpp:93:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   93 |     for (int i = 1; i <= n; i ++)
      |     ^~~
diversity.cpp:97:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |         ans = 1e18;
      |         ^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 26.0

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

Subtask #6
0 / 36.0

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