QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638625#6618. Encoded Strings IIjty233WA 203ms89420kbC++233.5kb2024-10-13 16:25:562024-10-13 16:26:01

Judging History

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

  • [2024-10-13 16:26:01]
  • 评测
  • 测评结果:WA
  • 用时:203ms
  • 内存:89420kb
  • [2024-10-13 16:25:56]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
using i64 = long long;
using u64 = unsigned i64;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    constexpr int S = 20;

    int T = 1;// cin >> T;
    while(T--){
        int n; cin >> n;
        string str; cin >> str;
        array<vector<int>, S> pre;
        pre.fill(vector<int>(n+1, 0));
        array<int, S+1> last; last.fill(0); last[S] = n;
        for(int j=0; j<S; j++){
            for(int i=1, cnt=0; i<=n; i++){
                pre[j][i] = pre[j][i-1] + (str[i-1]==j+'a');
            }
            last[j] = lower_bound(pre[j].begin(), pre[j].end(), pre[j][n]) - pre[j].begin();
        }

        // using State = vector<short>;
        constexpr u64 MASK = 0x3FF;
        struct State{
            array<int, S> v;
            void set(int i, int val){
                v[i] = val;
            }
            int get(int i){
                return v[i];
            }
            inline bool operator>(const State&o)const{
                return v > o.v;
            }
        };
        // struct State{
        //     // 10 * 20 == 200
        //     u64 v[4] = {0, 0, 0, 0};
        //     inline void set_v(int i, int j, u64 val){
        //         v[i] &= ~(MASK << (50 - j*10));
        //         v[i] |= (val & MASK) << (50 - j*10);
        //     }
        //     inline void set(int i, u64 val){
        //         // if(val == 0) return;
        //         set_v(i/6, i%6, val);
        //     }
        //     inline u64 get_v(int i, int j){
        //         return (v[i] >> (50 - j*10)) & MASK;
        //     }
        //     inline u64 get(int i){
        //         return get_v(i/6, i%6);
        //     }
        //     inline bool operator>(const State&o)const{
        //         if(v[0] != o.v[0]) return v[0] > o.v[0];
        //         if(v[1] != o.v[1]) return v[1] > o.v[1];
        //         if(v[2] != o.v[2]) return v[2] > o.v[2];
        //         return v[3] > o.v[3];
        //     }
        // };

        auto lowbit = [](auto x){
            return x&-x;
        };

        constexpr int N = 1<<S;
        vector<pair<State, int>> dp(N);
        dp[0] = {{}, 0};
        for(int s=0; s<N; s++){
            int cnt = __builtin_popcount(s);
            auto&[state, pos] = dp[s];
            auto mx=1<<S;
            for(int j=s^(N-1); j; j-=lowbit(j)){
                auto k = lowbit(j);
                if(last[__lg(mx)] > last[__lg(k)]){
                    mx = k;
                }
            }
            for(int j=s^(N-1); j; j-=lowbit(j)){
                auto k = lowbit(j);
                auto bound = last[__lg(mx)];
                auto ki = __lg(k);
                auto new_state = state;
                new_state.set(cnt, pre[ki][bound] - pre[ki][pos]);
                // cout << "bound[" << ki <<  "]: " << bound << " " << pos << " => " << pre[ki][bound] - pre[ki][pos] << endl;
                if(new_state > dp[s|k].first){
                    dp[s|k].first = std::move(new_state);
                    dp[s|k].second = lower_bound(pre[ki].begin(), pre[ki].end(), pre[ki][bound]) - pre[ki].begin();
                }
            }
        }
        char c = 'a' + S - 1;
        for(int i=0; i<S; i++){
            int x = dp[N-1].first.get(i);
            // cout << x << endl;
            while(x--) cout << c;
            c--;
        }
        cout << endl;
    }

    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 188ms
memory: 89420kb

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

score: 0
Accepted
time: 197ms
memory: 89224kb

input:

4
acac

output:

bba

result:

ok single line: 'bba'

Test #3:

score: 0
Accepted
time: 193ms
memory: 89308kb

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

score: 0
Accepted
time: 195ms
memory: 89212kb

input:

12
bcabcabcbcbb

output:

ccbbaa

result:

ok single line: 'ccbbaa'

Test #5:

score: 0
Accepted
time: 198ms
memory: 89244kb

input:

1000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'

Test #6:

score: 0
Accepted
time: 189ms
memory: 89312kb

input:

1000
ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

result:

ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'

Test #7:

score: 0
Accepted
time: 187ms
memory: 89284kb

input:

1000
edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...

output:

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

result:

ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'

Test #8:

score: 0
Accepted
time: 193ms
memory: 89376kb

input:

1000
hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...

output:

ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddccbbbaaa

result:

ok single line: 'dddddddddddddddddddddddddddddd...dddddddddddddddddddddddccbbbaaa'

Test #9:

score: 0
Accepted
time: 188ms
memory: 89312kb

input:

1000
cceooojojcecesjojsssesjojccoecceoojecsscojsosoccojscjcjssococjscssosecooeejoosojeecjceoeeojcocosjcecocoesjceejjecssjejccjsjosjsjcjesjojcojocjjeooeccojjosjcjjcjoecseecsjccojcoessecejcocosecsojeoceejeccejeoosssscecjcssooojoseeccosocoeejjecsjeoecejsoojessoescecjjsscecoccjsjsscccssjoeejsscoesecssco...

output:

eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeddccbaaa

result:

ok single line: 'eeeeeeeeeeeeeeeeeeeeeeeeeeeeee...eeeeeeeeeeeeeeeeeeeeeeeddccbaaa'

Test #10:

score: 0
Accepted
time: 194ms
memory: 89216kb

input:

1000
mmmfqfmpqrccmqfcrprpfppcpcffqcrcrcqmmmqmrfmrpqffppcmqpqqrfqqcffpmqqfmcmpmcfcqcffqmrmqrmmqmffpqqpfqrcppmmpmrqffmfcfffqmrprfcpfqffrrrmcqmpfmpfmprmcrrqqrmcrcmpcffmpfcprmcpmcfmpcfprrqrpcqccpcmmqcqqfmrcrrqrqcmcpqcrcqcrrpmpmfccqcffrrfmpfqqmqcpmfpmqpcmqpmfqpffmqpcrmcmqrqfqqcrfffcfqprcprrmfppfpqqmmrcmc...

output:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeeeeddcbaa

result:

ok single line: 'ffffffffffffffffffffffffffffff...fffffffffffffffffffffeeeeddcbaa'

Test #11:

score: 0
Accepted
time: 193ms
memory: 89380kb

input:

1000
hljikoiljhkhhikjihlhokhjnjlijjhkhinohnioklilhonihliiiohllkniiokjiihkokkkhnijkkkijnnjljoihiljlnjhllnjlhojnjojnnjhllilnnoloiijioiohkononkijhniihjiinononokjjokljjkinonhkojknohijhlilhjjlhkhjoonojlknjnljniklohinhinnnkhnkljjknkjhhlhlkllihhihnlkjklhokkihlhlikjhkjokhkniooljkojjiiljjjnojkiojnkniljnkoljn...

output:

ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggfeedccccbaa

result:

ok single line: 'gggggggggggggggggggggggggggggg...ggggggggggggggggggggfeedccccbaa'

Test #12:

score: 0
Accepted
time: 196ms
memory: 89420kb

input:

1000
cbpfmafbflfblamcccmcbbfqqfpbaaqfpccqqbqfcabmlbbmfqcpfqmcpqcfffacqbpbllappmbmcfpqqfqlcbcaclbbfqmqfqlammbcqblbccqcpabapcbbfcmpfcmmcpccbcbcfblfclmflpfaqppqbfppfpacmfqqafcmlmbqcbbfqaqffpafcbcqfpqmpcabfmcqcqpblfccmffplcbbaamcallbblmbcmammaablfmbfqqlcqacpqfaqpfcbamamcqcmqqffqfcbcffmabcfplabbmfqcampqc...

output:

hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhgggfedcba

result:

ok single line: 'hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...hhhhhhhhhhhhhhhhhhhhhhgggfedcba'

Test #13:

score: 0
Accepted
time: 192ms
memory: 89208kb

input:

1000
oikrbsjdjjsrcdbroobidjojkdjikbirccicdiicbskkciijkssjirjokcjosbbkcdkbrdroirsooiibsjokircbkjbrbkoobkrddcbossoskosbiksodsjkkocoricjkdscdickjdisiddbsdiikdisdcjdkddscdjjrkkddjbbbdidkidddijbibdisbicjokodrcbjkkcrokiciijssjjbscrssccckdjdirbbcocjkobrijssijjcjrcskdobrjcscbocoobdocobrorosiidoscrijjorsrirk...

output:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiihgfeedcba

result:

ok single line: 'iiiiiiiiiiiiiiiiiiiiiiiiiiiiii...iiiiiiiiiiiiiiiiiiiiiihgfeedcba'

Test #14:

score: 0
Accepted
time: 203ms
memory: 89284kb

input:

1000
cmctnhnrhchdnnaitttiirathamrkhtahnmrttkrhdimhatrttatrtmkiminahadihkdkrdthrkrhiandtmhtrdtiinicrmmirinnarkanadnhaatkkakarirnahrtcndarniihkdnddkhitkmdrtarhinirccaitdccnncnmnanhmtrdthkrmakdkktnimictdanrcmrhtcakmcmnahcrahkhtmadmhkrriinakkrhhddmnaknacchtacaktdnmaihnhcmtcchrdmihritatkactmmhattcrkknnkr...

output:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjiiihhhhgggfeeedccbaa

result:

ok single line: 'jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...jjjjjjjjjjjiiihhhhgggfeeedccbaa'

Test #15:

score: 0
Accepted
time: 189ms
memory: 89360kb

input:

1000
bcqeheddhchrddimchmikdfsmimikchdmmbreskiqfbikcdfhhmfbmqrmsibihciqqqsefmebmrbmcedhmdkmiqbdhsmkcqkifmiddhfieqersmksfiidqesisffhhrsbkiddbkbksrchchccifqkciidibqssihmmfrmfbeffhhqdbhmmdsisqkhqmhsmhckbccfreihdreiqqfcdsfffdbhsicbqfirhhchemfihedrbbkekhsfcccfmmieqfrrimsfddbqmkemciqfqrfbsresbhsiceffebfkfd...

output:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllkkkkkkjjihgggfedcba

result:

ok single line: 'llllllllllllllllllllllllllllll...llllllllllllkkkkkkjjihgggfedcba'

Test #16:

score: 0
Accepted
time: 195ms
memory: 89244kb

input:

1000
pdipkeekpamgdiiafeigfaaoktngfpmkggmkdmaicekcoggpattofngagapfaifodftdmkfoctpdkkomkttgpotdggeeonkdieocdcdnffiittompaopieonamnpiigienpenieaigfiieaeiiftmpkaaegopdeamatngamagapfnppkgciptpnmpcmiagfdoaiemftddddenikaiidmmdopfapgnmefdidgdkegofmeofnetktinipopkfdpkikcodtkapngefetkaffgppkkieikmfadottcceipk...

output:

mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmlllkjjjjiiihggfedcba

result:

ok single line: 'mmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...mmmmmmmmmmmlllkjjjjiiihggfedcba'

Test #17:

score: 0
Accepted
time: 186ms
memory: 89236kb

input:

1000
redfdnprmcbbhfdlmepnolpfotdhlrrlbedeccnrdblprfbdptohmbldthoorcrnceelhochsrppfbotmlchhsftlemfhbcnpdltofescnhmdhombpcddpscfhnmrnordbehnpdlrbbbfcdsoohpbhtcpsrhffobpehhdtmfcmmsbnpcedtmpfcpfporehfbfbotcpbeobnlednofedbpldcrosfcfnplnhbdlohfedrpsosmrpedenpfrrnsbehslloeldemsoeenfrsssppldtnfelrlboepptlpo...

output:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnmmllkkjjihhhhgfeeeeddcba

result:

ok single line: 'nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...nnnnnnnmmllkkjjihhhhgfeeeeddcba'

Test #18:

score: -100
Wrong Answer
time: 201ms
memory: 89380kb

input:

1000
hegsdmeapjipglsnfmianparlaersaragrlepapooflllgnsiggjdjdpraslojdfdaaesfpllhnihselidejrgrfmmaldfnrejophlanehrdsjrrsidomemhmeafrgrrajrrfrjjgpfmgsprifnolfglhmnfapljamsldgrfsomopfedsegdadmojparrssjpfsfaporljfhsfhhgrnilmhdlppoldhaomrjprnfirlmnnhfseofjenrohflfndfiimmsirjopeeipafhphogsafrngjjiprnifeila...

output:

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooonnmllkjjiihhggfedcbbba

result:

wrong answer 1st lines differ - expected: 'oooooooooooooooooooooooooooooo...oooooooonnmllkjjiihhggfedcbbbba', found: 'oooooooooooooooooooooooooooooo...ooooooooonnmllkjjiihhggfedcbbba'