oj.uz

Submission #878791

# Submission time Handle Problem Language Result Execution time Memory
878791 2023-11-25T08:33:57 Z niter Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 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], 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);
}

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);
    int tmp, 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 >> 1) << '\n';
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:99:9: warning: unused variable 'tmp' [-Wunused-variable]
   99 |     int tmp, start = 0;
      |         ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 444 KB Output is correct
2 Correct 480 ms 592 KB Output is correct
3 Correct 480 ms 344 KB Output is correct
4 Correct 480 ms 444 KB Output is correct
5 Correct 479 ms 344 KB Output is correct
6 Correct 480 ms 448 KB Output is correct
7 Correct 480 ms 460 KB Output is correct
8 Correct 479 ms 348 KB Output is correct
9 Correct 478 ms 596 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 444 KB Output is correct
2 Correct 480 ms 592 KB Output is correct
3 Correct 480 ms 344 KB Output is correct
4 Correct 480 ms 444 KB Output is correct
5 Correct 479 ms 344 KB Output is correct
6 Correct 480 ms 448 KB Output is correct
7 Correct 480 ms 460 KB Output is correct
8 Correct 479 ms 348 KB Output is correct
9 Correct 478 ms 596 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 444 KB Output is correct
2 Correct 479 ms 596 KB Output is correct
3 Correct 479 ms 348 KB Output is correct
4 Correct 480 ms 452 KB Output is correct
5 Correct 480 ms 348 KB Output is correct
6 Correct 480 ms 452 KB Output is correct
7 Correct 479 ms 592 KB Output is correct
8 Correct 479 ms 452 KB Output is correct
9 Correct 480 ms 452 KB Output is correct
10 Correct 480 ms 596 KB Output is correct
11 Correct 479 ms 348 KB Output is correct
12 Correct 480 ms 468 KB Output is correct
13 Correct 480 ms 348 KB Output is correct
14 Correct 479 ms 452 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 420 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 444 KB Output is correct
2 Correct 480 ms 592 KB Output is correct
3 Correct 480 ms 344 KB Output is correct
4 Correct 480 ms 444 KB Output is correct
5 Correct 479 ms 344 KB Output is correct
6 Correct 480 ms 448 KB Output is correct
7 Correct 480 ms 460 KB Output is correct
8 Correct 479 ms 348 KB Output is correct
9 Correct 478 ms 596 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 -