Submission #878800

#	Time	Username	Problem	Language	Result	Execution time	Memory
878800		niter	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1075 ms	472 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());

int a[405], b[405], cnt[5], cntb[5];
inline int rng(int l, int r){
    return uniform_int_distribution<int>(l, r)(RNG);
}

inline bool gen(int n, int st){
    cntb[1] = cnt[1];
    cntb[2] = cnt[2];
    cntb[3] = cnt[3];
    cntb[st]--;
//    entr
    b[0] = st;
//    loop(i,1,4){
//        ops(cntb[i]) spac
//    } entr
    int tmp = 0;
    loop(i,1,n){
        int choose = rng(1, 3);
        tmp = 0;
        while(cntb[choose] == 0 || b[i-1] == choose){
            choose = (choose == 3) ? (1) : (choose + 1);
            tmp++;
            if(tmp >= 3) return true;
        }
        cntb[choose]--;
        b[i] = choose;
//        loop(i,1,4){
//            ops(cntb[i]) spac
//        } entr
    }
    return false;
}
int ans;
queue<int> Qfrom[5], Qto[5];
inline void cac(int n){
    int tmp = 0;
    loop(i,0,n){
        if(Qto[a[i]].empty()){
            Qfrom[a[i]].push(i);
        }
        else{
            tmp += i - Qto[a[i]].front();
            Qto[a[i]].pop();
        }
        if(Qfrom[b[i]].empty()){
            Qto[b[i]].push(i);
        }
        else{
            tmp += i - Qfrom[b[i]].front();
            Qfrom[b[i]].pop();
        }
    }
    ans = min(ans, tmp);
}
bool check(int n){
    loop(i,0,n-1){
        if(b[i] == b[i+1]){
            return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
//    freopen("in.txt", "r", stdin);
    int n; string s;
    cin >> n >> s;
    loop(i,0,n){
        if(s[i] == 'R') a[i] = 1;
        else if(s[i] == 'G') a[i] = 2;
        else a[i] = 3;
        cnt[a[i]]++;
//        b[i] = a[i];
    }
    int max_cnt = max(max(cnt[1], cnt[2]), cnt[3]);
    int no_ans_lim;
    if(n % 2 == 1){
        no_ans_lim = (n + 1) / 2;
    }
    else{
        no_ans_lim = n / 2;
    }
    if(max_cnt > no_ans_lim){
        cout << "-1\n";
        return 0;
    }
    ans = n * (n - 1);
    loop(i,0,n) b[i] = a[i];
    sort(b, b + n);
    do{
        if(check(n)){
            cac(n);
        }
    }while(next_permutation(b, b + n));
    cout << (ans >> 1) << '\n';
}

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