Submission #519644

#	Time	Username	Problem	Language	Result	Execution time	Memory
519644		Giantpizzahead	Rope (JOI17_rope)	C++17	100 / 100	1355 ms	65196 KiB

rope

/*
Solution: 
Runtime: 
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;

const int MAXN = 1e6+5;
const int INF = 1e9;

int N, M;
int C[MAXN], saved[MAXN], ans[MAXN];
vector<pair<int, int>> toTry;
map<pair<int, int>, int> conflicts;

void solve() {
    cin >> N >> M;
    rep(i, 0, N) {
        cin >> C[i];
        C[i]--;
    }
    rep(i, 0, M) ans[i] = INF;

    // Pairs start at even indexes
    for (int i = 0; i < N; i += 2) {
        if (i == N-1) {
            // Final one
            saved[C[i]]++;
        } else {
            // Pair
            int j = i+1;
            if (C[i] == C[j]) saved[C[i]] += 2;
            else {
                saved[C[i]]++;
                saved[C[j]]++;
                pair<int, int> p = {min(C[i], C[j]), max(C[i], C[j])};
                conflicts[p]++;
            }
        }
    }
    // Sort best colors to pair with
    rep(i, 0, M) toTry.push_back({saved[i], i});
    sort(all(toTry));
    reverse(all(toTry));
    // Update answer for each
    rep(a, 0, M) {
        // Change all to one color
        ans[a] = min(N - saved[a], ans[a]);
        for (auto& p : toTry) {
            int b = p.second;
            if (a == b) continue;
            auto ptr = conflicts.find({min(a, b), max(a, b)});
            if (ptr == conflicts.end()) {
                // This is the best pairing; can stop here
                ans[a] = min(N - saved[a] - saved[b], ans[a]);
                break;
            } else {
                // Process manually and continue searching
                ans[a] = min(N - saved[a] - saved[b] + ptr->second, ans[a]);
            }
        }
    }

    // Pairs start at odd indexes
    rep(i, 0, M) saved[i] = 0;
    toTry.clear();
    conflicts.clear();
    for (int i = 1; i < N; i += 2) {
        if (i == N-1) {
            // Final one
            saved[C[i]]++;
        } else {
            // Pair
            int j = i+1;
            if (C[i] == C[j]) saved[C[i]] += 2;
            else {
                saved[C[i]]++;
                saved[C[j]]++;
                pair<int, int> p = {min(C[i], C[j]), max(C[i], C[j])};
                conflicts[p]++;
            }
        }
    }
    saved[C[0]]++;
    // Sort best colors to pair with
    rep(i, 0, M) toTry.push_back({saved[i], i});
    sort(all(toTry));
    reverse(all(toTry));
    // Update answer for each
    rep(a, 0, M) {
        // Change all to one color
        ans[a] = min(N - saved[a], ans[a]);
        for (auto& p : toTry) {
            int b = p.second;
            if (a == b) continue;
            auto ptr = conflicts.find({min(a, b), max(a, b)});
            if (ptr == conflicts.end()) {
                // This is the best pairing; can stop here
                ans[a] = min(N - saved[a] - saved[b], ans[a]);
                break;
            } else {
                // Process manually and continue searching
                ans[a] = min(N - saved[a] - saved[b] + ptr->second, ans[a]);
            }
        }
    }
    // debug << "toTry\n";
    // for (auto& p : toTry) debug << p.first << " " << p.second << endl;

    rep(i, 0, M) cout << ans[i] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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