#391421 (C++14) No.910 素数部分列

• 問題: No.910 素数部分列
• ユーザー: rtia_iidx
• 提出日時: 2019-10-18 23:13:03
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 92 ms / 1,000 ms
• コード長: 5,579 bytes
• コンパイル時間: 1,110 ms
• コンパイル使用メモリ: 111,880 KB
• 実行使用メモリ: 22,400 KB
• 最終ジャッジ日時: 2024-06-25 21:52:41
• 合計ジャッジ時間: 4,426 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	31 ms; 10,696 KB
testcase_24	AC	30 ms; 10,752 KB
testcase_25	AC	32 ms; 10,752 KB
testcase_26	AC	31 ms; 10,832 KB
testcase_27	AC	30 ms; 10,732 KB
testcase_28	AC	30 ms; 11,136 KB
testcase_29	AC	80 ms; 21,888 KB
testcase_30	AC	81 ms; 22,260 KB
testcase_31	AC	77 ms; 21,632 KB
testcase_32	AC	82 ms; 22,400 KB
testcase_33	AC	78 ms; 22,400 KB
testcase_34	AC	82 ms; 22,272 KB
testcase_35	AC	80 ms; 22,272 KB
testcase_36	AC	74 ms; 22,272 KB
testcase_37	AC	80 ms; 22,272 KB
testcase_38	AC	75 ms; 22,400 KB
testcase_39	AC	82 ms; 22,400 KB
testcase_40	AC	77 ms; 22,400 KB
testcase_41	AC	80 ms; 22,272 KB
testcase_42	AC	74 ms; 22,400 KB
testcase_43	AC	78 ms; 22,272 KB
testcase_44	AC	79 ms; 22,400 KB
testcase_45	AC	78 ms; 22,272 KB
testcase_46	AC	79 ms; 22,400 KB
testcase_47	AC	79 ms; 22,400 KB
testcase_48	AC	76 ms; 22,400 KB
testcase_49	AC	91 ms; 22,272 KB
testcase_50	AC	92 ms; 22,272 KB
testcase_51	AC	3 ms; 5,376 KB
testcase_52	AC	85 ms; 22,400 KB

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>
#include<list>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n,ll mod = MOD){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%mod;
        }
        x = (x*x)%mod;
        n >>= 1;
    }
    return ret;
}

ll mygcd(ll a,ll b){
    if(b == 0)return a;
    return mygcd(b,a%b);
}

ll twoPow(ll shiftNum){
    return (1LL << (shiftNum - 1));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    ll n;
    cin >> n;

    string str;

    cin >> str;

    set<ll> st1,st2,st3;

    ll ans = 0;

    for(int i = 0; i < n; i++){
        if(str[i] == '3' || str[i] == '7' || str[i] == '5'){
            ans++;
        }else if(str[i] == '1'){
            st1.insert(i);
        }else{
            st3.insert(i);
        }
    }

    /*while(true){
        auto itr = st2.begin();
        if(itr == st2.end())break;
        auto r = st3.upper_bound(*itr);
        if(r != st3.end()){
            ans++;
            st2.erase(itr);
            st3.erase(r);
        }else{
            break;
        }
    }*/

    auto st1c = st1;
    auto st3c = st3;

    auto tmpans = ans;

    while(true){
        auto itr = st3.begin();
        if(itr == st3.end()){
            break;
        }
        bool check = true;
        auto m = st3.upper_bound(*itr);
        if(m != st3.end()){
            auto r = st1.upper_bound(*m);
            if(r != st1.end()){
                ans++;
                st3.erase(itr);
                st1.erase(r);
                st3.erase(m);
            }else{
                check = false;
            }
        }else{
            break;
        }
        if(!check){
            break;
        }
    }

    while(true){
        auto itr = st1.begin();
        if(itr == st1.end()){
            break;
        }
        auto r = st3.upper_bound(*itr);
        if(r != st3.end()){
            ans++;
            st1.erase(itr);
            st3.erase(r);
        }else{
            break;
        }
    }

    while(true){
        auto itr = st1.begin();
        if(itr == st1.end()){
            break;
        }
        auto r = st1.upper_bound(*itr);
        if(r != st1.end()){
            ans++;
            st1.erase(itr);
            st1.erase(r);
        }else{
            break;
        }
    }

    ll t = ans;
    ans = tmpans;
    st1 = st1c;
    st3 = st3c;

    while(true){
        auto itr = st1.begin();
        if(itr == st1.end()){
            break;
        }
        auto r = st3.upper_bound(*itr);
        if(r != st3.end()){
            ans++;
            st1.erase(itr);
            st3.erase(r);
        }else{
            break;
        }
    }

    while(true){
        auto itr = st3.begin();
        if(itr == st3.end()){
            break;
        }
        bool check = true;
        auto m = st3.upper_bound(*itr);
        if(m != st3.end()){
            auto r = st1.upper_bound(*m);
            if(r != st1.end()){
                ans++;
                st3.erase(itr);
                st1.erase(r);
                st3.erase(m);
            }else{
                check = false;
            }
        }else{
            break;
        }
        if(!check){
            break;
        }
    }

    

    while(true){
        auto itr = st1.begin();
        if(itr == st1.end()){
            break;
        }
        auto r = st1.upper_bound(*itr);
        if(r != st1.end()){
            ans++;
            st1.erase(itr);
            st1.erase(r);
        }else{
            break;
        }
    }

    /*while(true){
        auto itr = st1.begin();
        if(itr == st1.end()){
            break;
        }
        bool check = true;
        auto m = st2.upper_bound(*itr);
        if(m != st2.end()){
            auto r = st1.upper_bound(*m);
            if(r != st1.end()){
                ans++;
                st1.erase(itr);
                st1.erase(r);
                st2.erase(m);
            }else{
                check = false;
            }
        }else{
            break;
        }
        if(!check){
            break;
        }
    }*/

    /*while(true){
        auto itr = st3.begin();
        if(itr == st3.end()){
            break;
        }
        bool check = true;
        auto m = st1.upper_bound(*itr);
        if(m != st1.end()){
            auto r = st1.upper_bound(*m);
            if(r != st1.end()){
                ans++;
                st3.erase(itr);
                st1.erase(r);
                st1.erase(m);
            }else{
                check = false;
            }
        }else{
            break;
        }
        if(!check){
            break;
        }
    }*/

    /*while(true){
        auto itr = st3.begin();
        if(itr == st3.end()){
            break;
        }
        bool check = true;
        auto m = st1.upper_bound(*itr);
        if(m != st1.end()){
            auto r = st3.upper_bound(*m);
            if(r != st3.end()){
                ans++;
                st3.erase(itr);
                st3.erase(r);
                st1.erase(m);
            }else{
                check = false;
            }
        }else{
            break;
        }
        if(!check){
            break;
        }
    }*/

    cout << max(ans,t) << endl;

    return 0;
}