oj.uz

Submission #878775

# Submission time Handle Problem Language Result Execution time Memory
878775 2023-11-25T08:06:44 Z niter Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 480 ms 596 KB 
#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];

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;
    }
    int ans = n * (n - 1), tmp;
    bool can;
    queue<int> Qfrom[5], Qto[5];
    while((long double)clock() / CLOCKS_PER_SEC <= 0.48){
        shuffle(b, b + n, RNG);
        can = true;
        loop(i,0,n-1){
            if(b[i] == b[i+1]){
                can = false;
                break;
            }
        }
        if(!can) continue;
        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();
            }
        }
//        ARR(b, n);
        ans = min(ans, tmp);
    }
    cout << (ans >> 1) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 452 KB Output is correct
2 Correct 479 ms 592 KB Output is correct
3 Correct 479 ms 344 KB Output is correct
4 Correct 480 ms 452 KB Output is correct
5 Correct 479 ms 448 KB Output is correct
6 Correct 479 ms 444 KB Output is correct
7 Correct 479 ms 596 KB Output is correct
8 Correct 479 ms 444 KB Output is correct
9 Correct 479 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Incorrect 480 ms 448 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 452 KB Output is correct
2 Correct 479 ms 592 KB Output is correct
3 Correct 479 ms 344 KB Output is correct
4 Correct 480 ms 452 KB Output is correct
5 Correct 479 ms 448 KB Output is correct
6 Correct 479 ms 444 KB Output is correct
7 Correct 479 ms 596 KB Output is correct
8 Correct 479 ms 444 KB Output is correct
9 Correct 479 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Incorrect 480 ms 448 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 448 KB Output is correct
2 Incorrect 479 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 452 KB Output is correct
2 Correct 479 ms 592 KB Output is correct
3 Correct 479 ms 344 KB Output is correct
4 Correct 480 ms 452 KB Output is correct
5 Correct 479 ms 448 KB Output is correct
6 Correct 479 ms 444 KB Output is correct
7 Correct 479 ms 596 KB Output is correct
8 Correct 479 ms 444 KB Output is correct
9 Correct 479 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Incorrect 480 ms 448 KB Output isn't correct
12 Halted 0 ms 0 KB -