oj.uz

Submission #876665

# Submission time Handle Problem Language Result Execution time Memory
876665 2023-11-22T07:51:59 Z parlimoos Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 1 ms 600 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define cl clear
#define bg begin
#define lb lower_bound
#define ub upper_bound
#define arr(x) array<int , x>
#define endl '\n'

int n;
string s;
int lt[400][3];
int rest , lest;
int o = 0;

void printList(){
    for(int i = lest ; i != -1 ; i = lt[i][2]){
        if(lt[i][1] == 1) cout << 'R';
        else if(lt[i][1] == 2) cout << 'Y';
        else cout << "G";
        // cout << i << " ";
    }
    cout << endl;
}
void buildList(){
    lest = 0;
    rest = n - 1;
    for(int i = 0 ; i < n ; i++){
        if(i == 0) lt[i][0] = -1;
        else lt[i][0] = i - 1;
        if(i == n - 1) lt[i][2] = -1;
        else lt[i][2] = i + 1;

        if(s[i] == 'R') lt[i][1] = 1;
        else if(s[i] == 'Y') lt[i][1] = 2;
        else lt[i][1] = 3;
    }
}
void connectList(int a , int l , int r){
    if(lt[a][0] != -1) lt[lt[a][0]][2] = lt[a][2];
    else lest = lt[a][2];
    if(lt[a][2] != -1) lt[lt[a][2]][0] = lt[a][0];
    else rest = lt[a][0];

    if(l != -1) lt[l][2] = a;
    else lest = a;
    if(r != -1) lt[r][0] = a;
    else rest = a;
    lt[a][0] = l , lt[a][2] = r;
}
int f1(){
    buildList();
    int res = 0;
    while(true){
        bool flag = false;
        int i = lest;
        int md;
        for(; lt[i][2] != -1 ; i = lt[i][2]){
            if(lt[i][1] == lt[lt[i][2]][1]){
                flag = true;
                md = lt[i][1];
                break;
            }
        }
        if(!flag) break;

        int mn1 = 1 , mn2 = 1;
        int j1 , j2;
        bool flg1 = false , flg2 = false;
        for(int k = i ; k != -1 ; k = lt[k][0]){
            if(lt[k][1] != md and (lt[k][0] == -1 or lt[lt[k][0]][1] != md)){
                j1 = k;
                flg1 = true;
                break;
            }else if(lt[k][1] != md) mn1++;
        }
        for(int k = i ; k != -1 ; k = lt[k][2]){
            if(lt[k][1] != md and (lt[k][2] == -1 or lt[lt[k][2]][1] != md)){
                j2 = k;
                flg2 = true;
                break;
            }else if(lt[k][1] != md) mn2++;
        }
        // cout << i << " , " << j1 << " " << j2 << "\n";
        if(!flg1 and !flg2){
            cout << "-1";
            exit(0);
        }else if((mn1 < mn2 or !flg2) and flg1){
            connectList(i , lt[j1][0] , j1);
            // cout << mn1 << "..\n";
            res += mn1;
        }else{
            connectList(i , j2 , lt[j2][2]);
            // cout << mn2 << "..\n";
            res += mn2;
        }
        // cout << md << " : ";
    }
    return res;
}
int f2(){
    buildList();
    int res = 0;
    while(true){
        bool flag = false;
        int i = rest;
        int md;
        for(; lt[i][0] != -1 ; i = lt[i][0]){
            if(lt[i][1] == lt[lt[i][0]][1]){
                flag = true;
                md = lt[i][1];
                break;
            }
        }
        if(!flag) break;

        int mn1 = 1 , mn2 = 1;
        int j1 , j2;
        bool flg1 = false , flg2 = false;
        for(int k = i ; k != -1 ; k = lt[k][0]){
            if(lt[k][1] != md and (lt[k][0] == -1 or lt[lt[k][0]][1] != md)){
                j1 = k;
                flg1 = true;
                break;
            }else if(lt[k][1] != md) mn1++;
        }
        for(int k = i ; k != -1 ; k = lt[k][2]){
            if(lt[k][1] != md and (lt[k][2] == -1 or lt[lt[k][2]][1] != md)){
                j2 = k;
                flg2 = true;
                break;
            }else if(lt[k][1] != md) mn2++;
        }
        // cout << i << " , " << j1 << " " << j2 << "\n";
        if(!flg1 and !flg2){
            cout << "-1";
            exit(0);
        }else if((mn1 <= mn2 or !flg2) and flg1){
            connectList(i , lt[j1][0] , j1);
            // cout << mn1 << "..\n";
            res += mn1;
        }else{
            connectList(i , j2 , lt[j2][2]);
            // cout << mn2 << "..\n";
            res += mn2;
        }
        // cout << md << " : ";
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    cin >> s;

    cout << min(f1() , f2());
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -