Submission #50115

#	Time	Username	Problem	Language	Result	Execution time	Memory
50115		SpaimaCarpatilor	Rope (JOI17_rope)	C++17	100 / 100	1884 ms	102840 KiB

rope

#include<bits/stdc++.h>

using namespace std;

int N, M, ans[1000009], g[1000009], h[1000009], a[1000009], id[1000009];
vector < int > v[1000009];

bool cmp (int i, int j)
{
    return (g[i] > g[j]);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=M; i++)
    ans[i] = N, id[i] = i;
for (int i=1; i<=N; i++)
    scanf ("%d", &a[i]), ans[a[i]] --;
for (int shift = 0; shift < 2; shift ++)
{
    int all = 0;
    for (int i=shift + 1; i<N; i+=2)
    {
        all ++;
        g[a[i]] ++, g[a[i + 1]] ++;
        if (a[i] != a[i + 1])
            v[a[i]].push_back (a[i + 1]),
            v[a[i + 1]].push_back (a[i]);
    }
    sort (id + 1, id + M + 1, cmp);
    for (int i=1; i<=M; i++)
    {
        for (auto j : v[i])
            h[j] ++;
        int extra = 0;
        if (shift == 1 && a[1] != i) h[a[1]] --, extra ++;
        if (shift != N % 2 && a[N] != i) h[a[N]] --, extra ++;

        ///min 2 * all + extra - g[i] - (g[j] - h[j]) = 2 * all + extra - g[i] - max (g[j] - h[j])
        int p = 1, curr = ans[i];
        while (p <= M && (h[id[p]] != 0 || id[p] == i)) p ++;
        if (p <= M)
            curr = min (curr, 2 * all + extra - g[i] - g[id[p]]);
        vector < int > currJ = v[i];
        if (shift == 1 && a[1] != i) currJ.push_back (a[1]);
        if (shift != N % 2 && a[N] != i) currJ.push_back (a[N]);
        for (auto j : currJ)
            curr = min (curr, 2 * all + extra - g[i] - (g[j] - h[j]));
        if (curr < ans[i])
            ans[i] = curr;
        ///
        for (auto j : v[i])
            h[j] --;
        if (shift == 1 && a[1] != i) h[a[1]] ++;
        if (shift != N % 2 && a[N] != i) h[a[N]] ++;
        /*for (int j=i + 1; j<=M; j++)
        {
            int curr = 2 * all - g[i] - g[j] + h[i][j];
            if (shift == 1) curr += (a[1] != i && a[1] != j);
            if (N % 2 != shift) curr += (a[N] != i && a[N] != j);
            if (curr < ans[i]) ans[i] = curr;
            if (curr < ans[j]) ans[j] = curr;
        }*/
    }
    for (int i=1; i<=M; i++)
        g[i] = h[i] = 0, v[i].clear ();
}
for (int i=1; i<=M; i++)
    printf ("%d\n", ans[i]);
return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:22:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &a[i]), ans[a[i]] --;
     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20