oj.uz

Submission #878806

# Submission time Handle Problem Language Result Execution time Memory
878806 2023-11-25T08:53:22 Z niter Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
20 / 100
 480 ms 692 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], c[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]--;
    b[0] = st;
    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;
    }
    return false;
}
int ans;
inline void cac(int n){
    int tmp = 0;
    loop(i,0,n) c[i] = a[i];
    loop(i,0,n){
        if(c[i] == b[i]) continue;
        loop(j,i+1,n){
            if(c[j] == b[i]){
                for(int k = j - 1; k >= i; k--){
                    swap(c[k], c[k + 1]);
                    tmp++;
                }
                break;
            }
        }
    }
    ans = min(ans, tmp);
}

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 = 1e9;
    int start = 0;
    while((long double)clock() / CLOCKS_PER_SEC <= 0.48){
        start = (start == 3) ? (1) : (start + 1);
        while(cnt[start] == 0)
            start = (start == 3) ? (1) : (start + 1);
        if(gen(n, start)) continue;
        cac(n);
    }
    cout << (ans) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 440 KB Output is correct
2 Correct 479 ms 444 KB Output is correct
3 Correct 479 ms 436 KB Output is correct
4 Correct 479 ms 348 KB Output is correct
5 Correct 479 ms 456 KB Output is correct
6 Correct 480 ms 592 KB Output is correct
7 Correct 479 ms 344 KB Output is correct
8 Correct 479 ms 344 KB Output is correct
9 Correct 480 ms 444 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 479 ms 440 KB Output is correct
12 Correct 480 ms 692 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 480 ms 440 KB Output is correct
15 Correct 480 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 440 KB Output is correct
2 Correct 479 ms 444 KB Output is correct
3 Correct 479 ms 436 KB Output is correct
4 Correct 479 ms 348 KB Output is correct
5 Correct 479 ms 456 KB Output is correct
6 Correct 480 ms 592 KB Output is correct
7 Correct 479 ms 344 KB Output is correct
8 Correct 479 ms 344 KB Output is correct
9 Correct 480 ms 444 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 479 ms 440 KB Output is correct
12 Correct 480 ms 692 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 480 ms 440 KB Output is correct
15 Correct 480 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 479 ms 436 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 440 KB Output is correct
2 Correct 479 ms 440 KB Output is correct
3 Correct 480 ms 348 KB Output is correct
4 Correct 479 ms 436 KB Output is correct
5 Correct 479 ms 344 KB Output is correct
6 Correct 480 ms 596 KB Output is correct
7 Correct 480 ms 440 KB Output is correct
8 Correct 479 ms 592 KB Output is correct
9 Correct 479 ms 348 KB Output is correct
10 Correct 479 ms 444 KB Output is correct
11 Correct 480 ms 440 KB Output is correct
12 Correct 479 ms 444 KB Output is correct
13 Correct 479 ms 344 KB Output is correct
14 Correct 480 ms 596 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 440 KB Output is correct
2 Correct 479 ms 444 KB Output is correct
3 Correct 479 ms 436 KB Output is correct
4 Correct 479 ms 348 KB Output is correct
5 Correct 479 ms 456 KB Output is correct
6 Correct 480 ms 592 KB Output is correct
7 Correct 479 ms 344 KB Output is correct
8 Correct 479 ms 344 KB Output is correct
9 Correct 480 ms 444 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 479 ms 440 KB Output is correct
12 Correct 480 ms 692 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 480 ms 440 KB Output is correct
15 Correct 480 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 479 ms 436 KB Output isn't correct
19 Halted 0 ms 0 KB -