Submission #762043

#	Time	Username	Problem	Language	Result	Execution time	Memory
762043		sysia	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	5 / 100	1079 ms	320 KiB

joi2019_ho_t3

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

int count(string &s, string t){
    int ret = 0;
    int n = (int)s.size();
    for (int i = 0; i<n; i++){
        if (s[i] == t[i]) continue;
        
        for (int j = i+1; j<n; j++){
            if (s[i] == t[j]){
                ret += (j-i);
                string r;
                for (int rep = 0; rep < i; rep++) r += s[rep];
                r += t[j];
                for (int rep = i; rep < n; rep++) {
                    if (rep == j) continue;
                    r += t[rep];
                }
                swap(t, r);
                break;
            }
        }
    }
    return ret;
}

void solve(){
    int n; cin >> n;
    string s; cin >> s;
    int r = 0, g = 0, y = 0;
    for (auto c: s){
        if (c == 'R') r++;
        if (c == 'G') g++;
        if (c == 'Y') y++;
    }
    int ans = oo;
    for (int mask = 0; mask < (1<<n); mask++){
        for (int submask = mask; ; submask = (submask-1)&mask){
            int R = __builtin_popcountll(submask);
            int G = __builtin_popcountll(mask) - R;
            int Y = n - __builtin_popcountll(mask);
            if (R != r || G != g || Y != y) {
                if (!submask) break;
                continue;
            }
            string t;
            for (int i = 0; i<n; i++){
                if (submask&(1<<i)){
                    t += 'R';
                } else if (mask&(1<<i)){
                    t += 'G';
                } else {
                    t += 'Y';
                }
            }
            bool ok = 1;
            for (int i = 1; i<n; i++){
                ok &= (t[i] != t[i-1]);
            }
            if (ok) ans = min(ans, count(s, t));
            if (!submask) break;
        }
    }
    if (ans == oo) cout << "-1\n";
    else cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

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