QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139410#4969. RCV SimplificationartcsAC ✓158ms18284kbC++173.0kb2023-08-13 12:38:382023-08-13 12:38:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-13 12:38:41]
  • 评测
  • 测评结果:AC
  • 用时:158ms
  • 内存:18284kb
  • [2023-08-13 12:38:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int,string>p1, pair<int,string>p2)
{
    return p1.first < p2.first;
}

bool cmp2(string p1, string p2)
{
    int tam = min(p1.length(), p2.length());
    
    for(int i=0;i<tam;i++)
    {
        char c1 = tolower(p1[i]), c2 = tolower(p2[i]);
        if( c1<c2)
            return true;
        if(c2<c1)
            return false;
    }
    return p1.length() < p2.length();

    
}


int main() {
    // your code goes here
    int n, tmp;
    cin>>n;
    
    string cad;
    map<string,int> V1;
    vector<string> names;

    int all =0;
    
    for(int i=0;i<n;i++)
    {
        cin>>cad;
        V1[cad]++;
        all++;
    }

    if(V1[cad]==n)
    {
        cout<<"0"<<endl;
        return 0;
    }
  
    bool band = true;

    map<string, int>:: iterator it;
    vector< pair<int, string > >resi;

    int additional = 0;
        
    band =false;
    int lowest = 1000000;
    for (it=V1.begin(); it!=V1.end(); ++it)
    {
        int p_c = (it->second);
        lowest = min(lowest, p_c);
    }
           
    for (it=V1.begin(); it!=V1.end(); ++it)
    {
        int p_c = (it->second);
        if(p_c == lowest)
        {
            names.push_back(it->first);
            additional+= it->second;
        }
        else
        {
            resi.push_back(pair<int,string>(it->second, it->first));
        }
    }

    
    if(int(resi.size()) !=0)
    {

        vector<int>cum;
        tmp = 0;

        sort(resi.begin(), resi.end(), cmp);
        for(int i=0;i<int(resi.size());i++)
        {
            cum.push_back(tmp+resi[i].first);
            tmp = cum[i];
        }

        int ind = 0;
        for(int i=0;i<int(resi.size())-1;i++)
        {
            //cout<<cum[i]+additional<<" "<<resi[i+1].first<<endl;            
            if(cum[i]+additional<resi[i+1].first)
                ind = i+1;
        } 
        for(int i=0;i<ind;i++)
            names.push_back(resi[i].second);

        //cout<<ind<<endl;

        if(ind == 0)
        {
            for(int i=0;i<int(resi.size())-1;i++)
            {
                if(cum[i]+additional==resi[i+1].first)
                    ind = i+1;
            }
            for(int i=0;i<ind;i++)
                names.push_back(resi[i].second);
        }
    }

//    vector<string> names_l;
//    map<string, string> NA;
//    int tam = names.size();
//
//    for(int i=0; i<tam;i++)
//    {
//        string s2 = names[i];
//        transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
//        names_l.push_back(s2);
//        NA[s2] = names[i];
//    }
//   
//
//    sort(names_l.begin(), names_l.end());
//    cout<<tam<<endl;
//    for(int i=0;i<tam;i++)
//        cout<<NA[names_l[i]]<<endl;
//
//

    int tam = names.size();
    sort(names.begin(), names.end());
    cout<<tam<<endl;
    for(int i=0;i<tam;i++)
        cout<<names[i]<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3580kb

input:

1
Alice

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 12ms
memory: 3480kb

input:

100000
Gisella
Jalal
Danecia
Jalal
Jalal
Gisella
Jalal
Jalal
Jalal
Jalal
Jalal
Jalal
Jalal
Jalal
Gisella
Jalal
Jesicca
Jalal
Carisa
Danecia
Jalal
Danecia
Jalal
Gisella
Jalal
Jalal
Danecia
Danecia
Jalal
Jalal
Danecia
Jalal
Jalal
Jalal
Jalal
Danecia
Jalal
Jalal
Jesicca
Danecia
Jalal
Jalal
Carisa
Danec...

output:

8
Carisa
Chantha
Danecia
Duran
Gared
Gisella
Jesicca
Shatia

result:

ok 9 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

2
Alice
Alice

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 15ms
memory: 3500kb

input:

100000
Shaul
Rasheedah
Ameisha
Rumaldo
Rumaldo
Ameisha
Sammuel
Shaul
Rea
Migdalia
Rasheedah
Migdalia
Migdalia
Shaul
Rumaldo
Shaul
Ameisha
Shaul
Ameisha
Rasheedah
Shaul
Rumaldo
Migdalia
Demetra
Sammuel
Rasheedah
Migdalia
Migdalia
Shaul
Nazario
Rasheedah
Migdalia
Shaul
Juanalberto
Juanalberto
Shaul
Sh...

output:

7
Ai
Hasan
Leeana
Lynden
Maia
Rojelio
Royal

result:

ok 8 lines

Test #5:

score: 0
Accepted
time: 158ms
memory: 18284kb

input:

100000
JarreauDunteDainelle
ToanTomyLarishaHardy
SharnetteRoxanViet
TajuanaSaraiJohnisha
SolanaLezlieRyon
TravonAriadne
PandoraMasielSmith
Davona
AshelyHensonShandia
Emmylou
ThayerPhillipeCoco
LaurelCandiaKaila
TyreikBoraBilly
MerrickLovelynShamar
RehamKhalishaLanee
LorindaDongRoneisha
Africa
MindyC...

output:

100000
Aadil
AadilCaela
AadilChi
AadilChiDomminic
Aaisha
AaishaDeshanaKelon
AaishaEdKatreseMarli
AaishaKatiann
Aakash
AakashDevonneKeryn
Aaliyah
AaliyahAlethia
AaliyahArleneLopaka
AaliyahElinaRendell
AaliyahJevin
AaliyahJevinWells
AaliyahKatiana
AaliyahPaschalGarvin
Aamanda
AamandaLylaShaqueena
Aama...

result:

ok 100001 lines

Test #6:

score: 0
Accepted
time: 11ms
memory: 3512kb

input:

65536
Eben
Kelsee
Kelsee
Eben
Kelsee
Eben
Kelsee
Eben
Darci
Eben
Neila
Eben
Eben
Darci
Natia
Kelsee
Eben
Eben
Neila
Kelsee
Kelsee
Eben
Kelsee
Eben
Neila
Eben
Eben
Kelsee
Eben
Darci
Eben
Kelsee
Eben
Eben
Eben
Eben
Eben
Eben
Kelsee
Eben
Eben
Eben
Eben
Eben
Kelsee
Darci
Eben
Darci
Eben
Darci
Hayes
Eben...

output:

16
Atara
Claudette
Courteney
Courtland
Curley
Dannon
Darci
Domanique
Hayes
Hoyt
Kelsee
Natia
Neila
Nial
Otisha
Tahesha

result:

ok 17 lines

Test #7:

score: 0
Accepted
time: 22ms
memory: 3604kb

input:

100000
Recardo
Tashenna
Judas
Queena
Diera
Lanaya
Eryka
Marcin
Ladonya
Shardi
Rajinder
Korrina
Dario
Kaija
Moncia
Cristin
Dorion
Imari
Devonne
Talonda
Cheree
Rito
Dai
Sheetal
Lucrecia
Breane
Jordyn
Sherri
Canon
Cristin
Hala
Concepcion
Augusta
Princella
Hobie
Talonda
Elexis
Abigael
Denna
Tyjuan
Risa
...

output:

2
Demitris
Phuong

result:

ok 3 lines

Test #8:

score: 0
Accepted
time: 92ms
memory: 8096kb

input:

100000
TaraannCrysten
EverttDavan
KaetlynTracyann
KaetlynTracyann
KaetlynTracyann
RicciKadenNickolas
KaetlynTracyann
KaetlynTracyann
KaetlynTracyann
KaetlynTracyann
Shalynn
Avery
HardyKejuan
KhariImberly
EvangeliaTrica
Amos
KaetlynTracyann
AsleyHayleyWest
SoylaSherrelCriselda
KaetlynTracyann
Kaetlyn...

output:

33515
Aadil
Aaisha
Aakash
AakashJuana
AakashJuanaAquilla
AakashJuanaLional
AakashYair
Aaliyah
AaliyahCelise
Aamanda
AamandaCigi
AamandaCigiTashana
Aamil
Aamir
Aaran
AaranAmbrose
AaranNeeraj
AaranNeerajRattana
Aaren
Aarica
AaricaRex
Aarik
AarikAbdullatif
AarikKim
Aarika
AarikaTavarus
Aarin
AarinGino
...

result:

ok 33516 lines