Submission #1130111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130111		am_aadvik	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	0 ms	324 KiB

joi2019_ho_t3

#include <iostream>
#include<vector>
using namespace std;

string alt(int n, bool c) { 
    string ans = ""; 
    while (n--) 
        ans += "RG"[c], c ^= 1;
    return ans;
}

int sol(string s, string t) { //s->t
    int n = s.length(), ans = 0;
    vector<int> nxtr(n + 1, -1), nxtg(n + 1, -1);
    for (int i = n - 1; i >= 0; --i) (nxtr[i] = (s[i] == 'R') ? i : nxtr[i + 1]);
    for (int i = n - 1; i >= 0; --i) (nxtg[i] = (s[i] == 'G') ? i : nxtg[i + 1]);
    for (int i = 0; i < n; ++i) 
        if (s[i] != t[i]) {
            int val = ((t[i] == 'R') ? nxtr[i] : nxtg[i]);
            ans += val - i, swap(s[i], s[val]);
        }
    return ans;
}

int32_t main()
{
    int n, r = 0, g = 0; cin >> n;
    string s, a1 = alt(n, 0), a2 = alt(n, 1); cin >> s;
    for (int i = 0; i < n; ++i)
        if (s[i] == 'R') r++;
        else g++;
    if (abs(g - r) > 1) {cout << -1; return 0;}
    
    int ans = 1e8;
    if (g >= r) ans = min(ans, sol(s, a2));
    if (r >= g) ans = min(ans, sol(s, a1));
    cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25