oj.uz

Submission #878787

# Submission time Handle Problem Language Result Execution time Memory
878787 2023-11-25T08:31:28 Z niter Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 480 ms 600 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], 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 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, start = 0;
    bool can;
    queue<int> Qfrom[5], Qto[5];
    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;
        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();
            }
        }
//        if(tmp < 16){
//            ARR(b, n);
//            op(tmp)
//            loop(i,1,4) op(cntb[i])
//            exit(0);
//        }
        ans = min(ans, tmp);
    }
    cout << (ans >> 1) << '\n';
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:77:10: warning: unused variable 'can' [-Wunused-variable]
   77 |     bool can;
      |          ^~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 600 KB Output is correct
2 Correct 479 ms 452 KB Output is correct
3 Correct 480 ms 448 KB Output is correct
4 Correct 480 ms 452 KB Output is correct
5 Correct 479 ms 452 KB Output is correct
6 Correct 479 ms 344 KB Output is correct
7 Correct 479 ms 344 KB Output is correct
8 Correct 480 ms 444 KB Output is correct
9 Correct 480 ms 348 KB Output is correct
10 Correct 480 ms 444 KB Output is correct
11 Correct 480 ms 448 KB Output is correct
12 Correct 479 ms 360 KB Output is correct
13 Correct 479 ms 596 KB Output is correct
14 Correct 479 ms 592 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 480 ms 348 KB Output is correct
2 Correct 479 ms 348 KB Output is correct
3 Correct 479 ms 444 KB Output is correct
4 Correct 479 ms 440 KB Output is correct
5 Correct 479 ms 448 KB Output is correct
6 Correct 480 ms 596 KB Output is correct
7 Correct 480 ms 348 KB Output is correct
8 Correct 480 ms 596 KB Output is correct
9 Correct 480 ms 444 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 480 ms 444 KB Output isn't correct
12 Halted 0 ms 0 KB -