Submission #1180329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180329		patgra	Rope (JOI17_rope)	C++20	55 / 100	2207 ms	327680 KiB

rope

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> iniCol(n);
    rep(i, 0, n) cin >> iniCol[i];
    vector<int> ans(m + 1, 1e9);
    map<pair<int, int>, int> ileTakich;
    vector<int> ilePojedynczych(m + 1, 0), ilePodwojnych(m + 1, 0);
    map<pair<int, int>, int> ileTakich2;
    vector<int> ilePojedynczych2(m + 1, 0), ilePodwojnych2(m + 1, 0);
    rep(i, 0, n - 1) {
        if(i % 2 == 0) {
            auto c1 = iniCol[i], c2 = iniCol[i + 1];
            if(c1 == c2) ilePodwojnych[c1]++;
            else ilePojedynczych[c1]++, ilePojedynczych[c2]++, ileTakich[pair{min(c1, c2), max(c1, c2)}]++;
        }
        else {
            auto c1 = iniCol[i], c2 = iniCol[i + 1];
            if(c1 == c2) ilePodwojnych2[c1]++;
            else ilePojedynczych2[c1]++, ilePojedynczych2[c2]++, ileTakich2[pair{min(c1, c2), max(c1, c2)}]++;
        } 
    }

    rep(c1, 1, m + 1) rep(c2, 1, m + 1) {
        int ileWsumie = n / 2;
        auto ilePoj = ilePojedynczych[c1] + (c1 == c2 ? 0 : ilePojedynczych[c2] - ileTakich[pair{min(c1, c2), max(c1, c2)}]);
        auto ilePod = ilePodwojnych[c1] + (c1 == c2 ? 0 : ilePodwojnych[c2]);
        int ileNie = ileWsumie - ilePod - ilePoj;
        auto cost1 = ileNie * 2 + ilePoj;
        if(n % 2 == 1) cost1 += iniCol.back() != c1 && iniCol.back() != c2;

        if(n % 2 == 0) ileWsumie--;
        ilePoj = ilePojedynczych2[c1] + (c1 == c2 ? 0 : ilePojedynczych2[c2] - ileTakich2[pair{min(c1, c2), max(c1, c2)}]);
        ilePod = ilePodwojnych2[c1] + (c1 == c2 ? 0 : ilePodwojnych2[c2]);
        ileNie = ileWsumie - ilePod - ilePoj;
        auto cost2 = ileNie * 2 + ilePoj;
        cost2 += iniCol[0] != c1 && iniCol[0] != c2;
        if(n % 2 == 0) cost2 += iniCol.back() != c1 && iniCol.back() != c2;

        auto cost = min(cost1, cost2);
        ans[c1] = min(ans[c1], cost);
        ans[c2] = min(ans[c2], cost);
    }

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

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