/** * JOI 2016/2017 Final Round - Task 5: Rope * Solution based on Pair Parity Observation. * * Logic: * The folding process partitions the rope into adjacent pairs that are merged. * We analyze adjacent pairs in different alignments (starting at index 0 or 1). * We aim to maximize matches for a Target Color C and an optimal Partner Color Y. */ #include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; const int INF = 1e9; // Global variables to store frequencies and answers int N, M; vector<int> ar; vector<int> ans; vector<int> app; // Total appearance count of each color vector<int> d; // Colors sorted by frequency // Updates the answer for color 'a' with a new minimum cost 'b' void chmin(int& a, int b) { if (b < a) a = b; } // Solver function for a specific sub-segment of the rope // n: length of the segment to consider // offset: starting index in the global array 'ar' // L, R: Boundary colors (leftover cords) that are NOT part of pairs // (passed as -1 if they don't exist in the current cut) void solve(int n, int offset, int L, int R) { // If n is odd, one element is left unpaired inside the range. // The passed L and R account for boundary "singletons". // 1. Identify pairs (u, v) in this alignment vector<pair<int, int>> ps; ps.reserve(n / 2); for (int i = 0; i < n - 1; i += 2) { int u = ar[offset + i]; int v = ar[offset + i + 1]; if (u > v) swap(u, v); ps.push_back({u, v}); } // Sort pairs to count unique overlaps efficiently sort(ps.begin(), ps.end()); // Unique the pairs to iterate distinct combinations vector<pair<int, int>> unique_ps = ps; unique_ps.erase(unique(unique_ps.begin(), unique_ps.end()), unique_ps.end()); // Count occurrences of each specific pair vector<int> pscnt(unique_ps.size(), 0); // Use lower_bound to find index in unique_ps for (size_t i = 0; i < ps.size(); ++i) { int idx = lower_bound(unique_ps.begin(), unique_ps.end(), ps[i]) - unique_ps.begin(); pscnt[idx]++; } // 2. Optimization 1: Calculate cost based on adjacent pairs found for (size_t i = 0; i < unique_ps.size(); ++i) { int u = unique_ps[i].first; int v = unique_ps[i].second; // Cost formula explanation: // We want to keep all 'u' and all 'v'. // Total instances = app[u] + app[v]. // However, pscnt[i] is the number of times u and v appear as a specific merged pair. // In those merged pairs, we gain +1 match total (either u or v matches), // whereas app[u]+app[v] counts +2. So we subtract pscnt[i] to correct the gain. // Total Gain = app[u] + app[v] - pscnt[i]. // Cost = Total_Rope_Length - Total_Gain. // Note: The rope length for cost calculation is the original N. int val = N - (app[u] + app[v] - pscnt[i]); chmin(ans[u], val); chmin(ans[v], val); } // 3. Optimization 2: Fallback for high-frequency colors that might NOT be adjacent // We try to pair color 'i' with the most frequent color 'j' such that // the pair (i, j) was NOT handled in the loop above (i.e., not strictly adjacent). // We iterate through colors sorted by frequency (descending) for (int i = 0; i < M; ++i) { int color_u = d[i]; // Find the best partner color_v (d[j]) int j = 0; while (j < M) { int color_v = d[j]; if (color_u == color_v) { j++; continue; } // Check if this pair (u, v) exists in the current adjacent pairing. // If it does, we already processed the optimal case for it in step 2. // If it does NOT, the overlap is 0, so Gain = app[u] + app[v]. // We check existence using binary search on unique_ps. int mn = min(color_u, color_v); int mx = max(color_u, color_v); if (binary_search(unique_ps.begin(), unique_ps.end(), make_pair(mn, mx))) { j++; // This pair was adjacent, so handled above. Skip. } else { // Found best non-adjacent partner. int val = N - (app[color_u] + app[color_v]); chmin(ans[color_u], val); chmin(ans[color_v], val); break; // Since d is sorted by frequency, the first valid j is the best. } } } } int main() { // Fast I/O ios_base::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> N >> M)) return 0; if (M == 1) { cout << "0\n"; return 0; } ar.resize(N); app.assign(M, 0); ans.assign(M, INF); for (int i = 0; i < N; ++i) { cin >> ar[i]; ar[i]--; // Convert to 0-based index app[ar[i]]++; } // Prepare 'd' array: colors sorted by frequency descending d.resize(M); for (int i = 0; i < M; ++i) d[i] = i; sort(d.begin(), d.end(), [&](int a, int b) { return app[a] > app[b]; }); // We try 4 configurations to cover all alignment parities and boundary conditions // 1. Full array, starting at 0 solve(N, 0, -1, -1); // 2. Skip first element, starting at 1 (Shifted alignment) solve(N - 1, 1, ar[0], -1); // 3. Skip last element (Alignment starting at 0, but N-1 length) solve(N - 1, 0, -1, ar[N - 1]); // 4. Skip first and last (Shifted alignment, N-2 length) solve(N - 2, 1, ar[0], ar[N - 1]); for (int i = 0; i < M; ++i) { cout << ans[i] << "\n"; } return 0; }