Submission #50111

#	Time	Username	Problem	Language	Result	Execution time	Memory
50111		SpaimaCarpatilor	Rope (JOI17_rope)	C++17	80 / 100	385 ms	79180 KiB

rope

#include<bits/stdc++.h>

using namespace std;

int N, M, ans[5009], h[5009][5009], g[5009], a[1000009];

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

scanf ("%d %d", &N, &M);
for (int i=1; i<=M; i++)
    ans[i] = N;
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]) h[a[i]][a[i + 1]] ++;
        else h[a[i + 1]][a[i]] ++;
    }
    for (int i=1; i<=M; i++)
        for (int j=i + 1; j<=M; j++)
        {
            int curr = 2 * (all - g[i] - g[j] + h[i][j] + h[i][i] + h[j][j]) +
                           (g[i] + g[j] - h[i][j] - 2 * h[i][i] - 2 * h[j][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=shift + 1; i<N; i+=2)
    {
        g[a[i]] --, g[a[i + 1]] --;
        if (a[i] < a[i + 1]) h[a[i]][a[i + 1]] --;
        else h[a[i + 1]][a[i]] --;
    }
}
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:12: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:16: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: 0 / 20