Submission #519645

#TimeUsernameProblemLanguageResultExecution timeMemory
519645GiantpizzaheadRope (JOI17_rope)C++17
100 / 100
1309 ms58392 KiB
/* 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 genPairs(bool isOdd) { // Clear previous data rep(i, 0, M) saved[i] = 0; toTry.clear(); conflicts.clear(); // Generate pairs for (int i = isOdd; 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]++; } } } if (isOdd) saved[C[0]]++; } void updateAns() { // 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]); } } } } 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 genPairs(false); updateAns(); // Pairs start at odd indexes genPairs(true); updateAns(); rep(i, 0, M) cout << ans[i] << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...