Submission #128129

#	Time	Username	Problem	Language	Result	Execution time	Memory
128129		EntityIT	Rope (JOI17_rope)	C++14	100 / 100	1160 ms	136716 KiB

rope

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

using ii = pair<int, int>;
int n, m;
vector<int> c, cnt, Cnt, order;
vector<bool> existed;
vector< vector<int> > vec[2];

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

int solve (int col, bool _) {
    int cnt_rem = n - cnt[col] - (int)vec[_][col].size();

    for (int _col : vec[_][col]) ++Cnt[_col], existed[_col] = 1;
    Cnt[col] = cnt[col]; existed[col] = 1;

    int mx = 0;
    for (int i = 0; i < m; ++i) {
        if (existed[ order[i] ]) mx = max(mx, cnt[ order[i] ] - Cnt[ order[i] ]);
        else { mx = max(mx, cnt[ order[i] ]); break; }
    }
    cnt_rem -= mx;

    for (int _col : vec[_][col]) Cnt[_col] = 0, existed[_col] = 0;
    Cnt[col] = 0; existed[col] = 0;

    return cnt_rem + (int)vec[_][col].size();
}



int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    existed.assign(m, 0);
    order.assign(m, 0);
    Cnt.assign(m, 0);
    cnt.assign(m, 0);
    c.assign(n, 0);
    for (int i = 0; i < n; ++i) cin >> c[i], --c[i], ++cnt[ c[i] ];

    for (int _ = 0; _ < 2; ++_) {
        vec[_].assign(m, vector<int>() );
        vector<int> sz_vec(m, 0);
        for (int i = _; i + 1 < n; i += 2) {
            if (c[i] != c[i + 1]) {
                ++sz_vec[ c[i] ];
                ++sz_vec[ c[i + 1] ];
            }
        }
        for (int i = 0; i < m; ++i) vec[_][i].assign(sz_vec[i], 0);
        sz_vec.assign(m, 0);
        for (int i = _; i + 1 < n; i += 2) {
            if (c[i] != c[i + 1]) {
                vec[_][ c[i] ][ sz_vec[ c[i] ]++ ] = c[i + 1];
                vec[_][ c[i + 1] ][ sz_vec[ c[i + 1] ]++ ] = c[i];
            }
        }
    }

    for (int i = 0; i < m; ++i) order[i] = i;
    sort(order.begin(), order.end(), cmp);

    for (int col = 0; col < m; ++col) cout << min(solve(col, 0), solve(col, 1) ) << '\n';

    return 0;
}

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