TopCoder SRM 696

250_Rope_String

class Ropestring {
public:
    string makerope(string s) {
        vector<int> even, odd;
        int size = (int)s.size();
        int cur = 0;
        for (int i = 0; i < size; ++i) {
            if (s[i] == '-')
                ++cur;
            if (s[i] == '.') {
                if (i > 0 && s[i - 1] == '-') {
                    if (cur % 2) {
                        odd.push_back(cur);
                    } else {
                        even.push_back(cur);
                    }
                    cur = 0;
                }
            }
        }
        if (s[size - 1] == '-') {
            if (cur % 2) {
                odd.push_back(cur);
            } else {
                even.push_back(cur);
            }
        }

        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());
        string ret;
        int count = 0;

        for (int i = (int)even.size() - 1; i >= 0; --i) {
            int size = even[i];
            while (size) {
                ret.push_back('-');
                ++count;
                --size;
            }
            if (i != 0) {
                ret.push_back('.'); ++count;
            }
        }

        if (!even.empty() && !odd.empty()) {
            ret.push_back('.'); ++count;
        }

        for (int i = (int)(odd.size() - 1); i >= 0; --i) {
            int size = odd[i];
            while (size) {
                ret.push_back('-');
                ++count;
                --size;
            }
            if (i != 0) {
                ret.push_back('.'); ++count;
            }
        }

        int left = (int)s.size() - count;
        while (left) {
            ret.push_back('.'); --left;
        }
        return ret;
    }
};

500_Array_Fix

class Arrfix {
public:
    int mindiff(vector <int> A, vector <int> B, vector <int> F) {
        unordered_map<int, int> hashb;
        unordered_map<int, int> hashf;
        for (auto &i : B) {
            hashb[i]++;
        }
        for (auto &i : F) {
            hashf[i]++;
        }

        int diff = 0;
        int size = (int)A.size();
        int used = 0;
        for (int i = 0; i < size; ++i) {
            if (A[i] == B[i])
                continue;
            if (hashf[B[i]]) {
                hashf[B[i]]--;
                ++used;
                hashb[B[i]]--;
                continue;
            }
            ++diff;
        }

        if (used == (int)F.size())
            return diff;

        for (auto iter = hashf.begin(); iter != hashf.end(); ++iter) {
            int key = iter->first;
            int count = iter->second;
            if (count == 0) continue;
            if (hashb[key]) {
                hashb[key]--;
            } else {
                ++diff;
            }
        }
        return diff;
    }
};