/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 492.0 KiB
#2 Accepted 8ms 784.0 KiB
#3 Accepted 17ms 732.0 KiB
#4 Wrong Answer 2ms 356.0 KiB
#5 Accepted 5ms 588.0 KiB
#6 Accepted 10ms 540.0 KiB
#7 Accepted 8ms 812.0 KiB
#8 Accepted 10ms 728.0 KiB
#9 Accepted 10ms 812.0 KiB

Code

/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
bool iscomp[20000];
vector<int> primes;
void seive()
{
    for(int i=2;i<20000;i++)
    {
        if(iscomp[i]) continue;
        for(int j=i+i;j<20000;j+=i) iscomp[j]=true;
    }
    primes.push_back(0);
    for(int i=2;i<3000;i++)
    {
        if(!iscomp[i]) primes.push_back(i);
    }
}

void solve()
{
    int n; cin >> n;
    string s; cin >> s;
    int a=0,b=0,c=0;
    for(auto e:s)
    {
        a += (e=='a');
        b += (e=='b');
        c += (e=='c');
    }
    vector<vector<int>> v;
    int m = primes.size();
    for(int i=0;i<m;i++)
    {
        for(int j=i;j<m;j++)
        {
            int need = n-primes[i]-primes[j];
            if(need < primes[j]) break;
            if(!iscomp[need]) v.push_back({primes[i],primes[j],need});
        }
    }
    if(v.empty()) {cout<<-1<<endl; return;}
    vector<int> abc;
    abc.push_back(a);
    abc.push_back(b);
    abc.push_back(c);
    sort(abc.begin(),abc.end());
    int ans = 1e9;
    for(auto e:v)
    {
        ans = min(ans , (abs(abc[0]-e[0])+abs(abc[1]-e[1])+abs(abc[2]-e[2]))/2 );
    }
    cout<<ans<<endl;
}

int main()
{
    seive();
    int t; cin >> t; while(t--) solve();
}

Information

Submit By
Type
Submission
Problem
P1158 Yet another Beautiful String
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-05 13:48:49
Judged At
2025-01-05 13:48:49
Judged By
Score
90
Total Time
17ms
Peak Memory
812.0 KiB