Submission #1173656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173656		LucaIlie	Rope (JOI17_rope)	C++20	55 / 100	2595 ms	4460 KiB

rope

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6;
const int MAX_M = 1e6;
int c[MAX_N], ans[MAX_M + 1], frecv[MAX_M + 1];

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int n, m;

    cin >> n >> m;
    for ( int i = 0; i < n; i++ ) 
        cin >> c[i];

    for ( int x = 1; x <= m; x++ ) {
        ans[x] = n;
        for ( int f = 0; f < 2; f++ ) {
            for ( int l = 0; l < 2; l++ ) {
                if ( (n - f - l) % 2 == 1 )
                    continue;

                int changes = 0;
                if ( f && c[0] != x )
                    frecv[c[0]]++;
                if ( l && c[n - 1] != x )
                    frecv[c[n - 1]]++;
                for ( int i = f; i < n - l; i += 2 ) {
                    if ( c[i] == x || c[i + 1] == x ) {
                        if ( c[i] != x || c[i + 1] != x )
                            changes++;
                    } else {
                        frecv[c[i]]++;
                        frecv[c[i + 1]]++;
                    }
                }
                int maxFrecv = 0;
                for ( int i = 1; i <= m; i++ ) {
                    maxFrecv = max( maxFrecv, frecv[i] );
                    changes += frecv[i];
                    frecv[i] = 0;
                }
                changes -= maxFrecv;
                ans[x] = min( ans[x], changes );
            }
        }
    }

    for ( int i = 1; i <= m; i++ )
        cout << ans[i] << "\n";

    return 0;
}

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