Submission #876665

#	Time	Username	Problem	Language	Result	Execution time	Memory
876665		parlimoos	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1 ms	600 KiB

joi2019_ho_t3

#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
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25