QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#638568 | #6618. Encoded Strings II | jty233 | WA | 104ms | 44472kb | C++23 | 3.3kb | 2024-10-13 16:15:07 | 2024-10-13 16:15:07 |
Judging History
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{
// 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, sc=mx;
for(int j=s^(N-1); j; j-=lowbit(j)){
auto k = lowbit(j);
if(last[__lg(mx)] > last[__lg(k)]){
sc = mx;
mx = k;
}else if(last[__lg(sc)] > last[__lg(k)]){
sc = k;
}
}
for(int j=s^(N-1); j; j-=lowbit(j)){
auto k = lowbit(j);
auto bound = k == mx ? last[__lg(sc)] : last[__lg(mx)];
auto ki = __lg(k);
auto new_state = state;
new_state.set(cnt, max(0, 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 = max<int>(pos, 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;
}
详细
Test #1:
score: 100
Accepted
time: 88ms
memory: 44152kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 87ms
memory: 44264kb
input:
4 acac
output:
bba
result:
ok single line: 'bba'
Test #3:
score: 0
Accepted
time: 97ms
memory: 44212kb
input:
1 t
output:
a
result:
ok single line: 'a'
Test #4:
score: 0
Accepted
time: 82ms
memory: 44064kb
input:
12 bcabcabcbcbb
output:
ccbbaa
result:
ok single line: 'ccbbaa'
Test #5:
score: 0
Accepted
time: 92ms
memory: 44264kb
input:
1000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
Test #6:
score: 0
Accepted
time: 89ms
memory: 44472kb
input:
1000 ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...
output:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
result:
ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'
Test #7:
score: 0
Accepted
time: 91ms
memory: 44252kb
input:
1000 edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'
Test #8:
score: 0
Accepted
time: 92ms
memory: 44348kb
input:
1000 hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...
output:
ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddccbbbaaa
result:
ok single line: 'dddddddddddddddddddddddddddddd...dddddddddddddddddddddddccbbbaaa'
Test #9:
score: 0
Accepted
time: 94ms
memory: 44276kb
input:
1000 cceooojojcecesjojsssesjojccoecceoojecsscojsosoccojscjcjssococjscssosecooeejoosojeecjceoeeojcocosjcecocoesjceejjecssjejccjsjosjsjcjesjojcojocjjeooeccojjosjcjjcjoecseecsjccojcoessecejcocosecsojeoceejeccejeoosssscecjcssooojoseeccosocoeejjecsjeoecejsoojessoescecjjsscecoccjsjsscccssjoeejsscoesecssco...
output:
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeddccbaaa
result:
ok single line: 'eeeeeeeeeeeeeeeeeeeeeeeeeeeeee...eeeeeeeeeeeeeeeeeeeeeeeddccbaaa'
Test #10:
score: 0
Accepted
time: 86ms
memory: 44420kb
input:
1000 mmmfqfmpqrccmqfcrprpfppcpcffqcrcrcqmmmqmrfmrpqffppcmqpqqrfqqcffpmqqfmcmpmcfcqcffqmrmqrmmqmffpqqpfqrcppmmpmrqffmfcfffqmrprfcpfqffrrrmcqmpfmpfmprmcrrqqrmcrcmpcffmpfcprmcpmcfmpcfprrqrpcqccpcmmqcqqfmrcrrqrqcmcpqcrcqcrrpmpmfccqcffrrfmpfqqmqcpmfpmqpcmqpmfqpffmqpcrmcmqrqfqqcrfffcfqprcprrmfppfpqqmmrcmc...
output:
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeeeeddcbaa
result:
ok single line: 'ffffffffffffffffffffffffffffff...fffffffffffffffffffffeeeeddcbaa'
Test #11:
score: 0
Accepted
time: 95ms
memory: 44332kb
input:
1000 hljikoiljhkhhikjihlhokhjnjlijjhkhinohnioklilhonihliiiohllkniiokjiihkokkkhnijkkkijnnjljoihiljlnjhllnjlhojnjojnnjhllilnnoloiijioiohkononkijhniihjiinononokjjokljjkinonhkojknohijhlilhjjlhkhjoonojlknjnljniklohinhinnnkhnkljjknkjhhlhlkllihhihnlkjklhokkihlhlikjhkjokhkniooljkojjiiljjjnojkiojnkniljnkoljn...
output:
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggfeedccccbaa
result:
ok single line: 'gggggggggggggggggggggggggggggg...ggggggggggggggggggggfeedccccbaa'
Test #12:
score: 0
Accepted
time: 91ms
memory: 44320kb
input:
1000 cbpfmafbflfblamcccmcbbfqqfpbaaqfpccqqbqfcabmlbbmfqcpfqmcpqcfffacqbpbllappmbmcfpqqfqlcbcaclbbfqmqfqlammbcqblbccqcpabapcbbfcmpfcmmcpccbcbcfblfclmflpfaqppqbfppfpacmfqqafcmlmbqcbbfqaqffpafcbcqfpqmpcabfmcqcqpblfccmffplcbbaamcallbblmbcmammaablfmbfqqlcqacpqfaqpfcbamamcqcmqqffqfcbcffmabcfplabbmfqcampqc...
output:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhgggfedcba
result:
ok single line: 'hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...hhhhhhhhhhhhhhhhhhhhhhgggfedcba'
Test #13:
score: 0
Accepted
time: 90ms
memory: 44324kb
input:
1000 oikrbsjdjjsrcdbroobidjojkdjikbirccicdiicbskkciijkssjirjokcjosbbkcdkbrdroirsooiibsjokircbkjbrbkoobkrddcbossoskosbiksodsjkkocoricjkdscdickjdisiddbsdiikdisdcjdkddscdjjrkkddjbbbdidkidddijbibdisbicjokodrcbjkkcrokiciijssjjbscrssccckdjdirbbcocjkobrijssijjcjrcskdobrjcscbocoobdocobrorosiidoscrijjorsrirk...
output:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiihgfeedcba
result:
ok single line: 'iiiiiiiiiiiiiiiiiiiiiiiiiiiiii...iiiiiiiiiiiiiiiiiiiiiihgfeedcba'
Test #14:
score: 0
Accepted
time: 87ms
memory: 44244kb
input:
1000 cmctnhnrhchdnnaitttiirathamrkhtahnmrttkrhdimhatrttatrtmkiminahadihkdkrdthrkrhiandtmhtrdtiinicrmmirinnarkanadnhaatkkakarirnahrtcndarniihkdnddkhitkmdrtarhinirccaitdccnncnmnanhmtrdthkrmakdkktnimictdanrcmrhtcakmcmnahcrahkhtmadmhkrriinakkrhhddmnaknacchtacaktdnmaihnhcmtcchrdmihritatkactmmhattcrkknnkr...
output:
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjiiihhhhgggfeeedccbaa
result:
ok single line: 'jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...jjjjjjjjjjjiiihhhhgggfeeedccbaa'
Test #15:
score: 0
Accepted
time: 104ms
memory: 44464kb
input:
1000 bcqeheddhchrddimchmikdfsmimikchdmmbreskiqfbikcdfhhmfbmqrmsibihciqqqsefmebmrbmcedhmdkmiqbdhsmkcqkifmiddhfieqersmksfiidqesisffhhrsbkiddbkbksrchchccifqkciidibqssihmmfrmfbeffhhqdbhmmdsisqkhqmhsmhckbccfreihdreiqqfcdsfffdbhsicbqfirhhchemfihedrbbkekhsfcccfmmieqfrrimsfddbqmkemciqfqrfbsresbhsiceffebfkfd...
output:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllkkkkkkjjihgggfedcba
result:
ok single line: 'llllllllllllllllllllllllllllll...llllllllllllkkkkkkjjihgggfedcba'
Test #16:
score: 0
Accepted
time: 101ms
memory: 44308kb
input:
1000 pdipkeekpamgdiiafeigfaaoktngfpmkggmkdmaicekcoggpattofngagapfaifodftdmkfoctpdkkomkttgpotdggeeonkdieocdcdnffiittompaopieonamnpiigienpenieaigfiieaeiiftmpkaaegopdeamatngamagapfnppkgciptpnmpcmiagfdoaiemftddddenikaiidmmdopfapgnmefdidgdkegofmeofnetktinipopkfdpkikcodtkapngefetkaffgppkkieikmfadottcceipk...
output:
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmlllkjjjjiiihggfedcba
result:
ok single line: 'mmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...mmmmmmmmmmmlllkjjjjiiihggfedcba'
Test #17:
score: 0
Accepted
time: 90ms
memory: 44344kb
input:
1000 redfdnprmcbbhfdlmepnolpfotdhlrrlbedeccnrdblprfbdptohmbldthoorcrnceelhochsrppfbotmlchhsftlemfhbcnpdltofescnhmdhombpcddpscfhnmrnordbehnpdlrbbbfcdsoohpbhtcpsrhffobpehhdtmfcmmsbnpcedtmpfcpfporehfbfbotcpbeobnlednofedbpldcrosfcfnplnhbdlohfedrpsosmrpedenpfrrnsbehslloeldemsoeenfrsssppldtnfelrlboepptlpo...
output:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnmmllkkjjihhhhgfeeeeddcba
result:
ok single line: 'nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...nnnnnnnmmllkkjjihhhhgfeeeeddcba'
Test #18:
score: -100
Wrong Answer
time: 91ms
memory: 44252kb
input:
1000 hegsdmeapjipglsnfmianparlaersaragrlepapooflllgnsiggjdjdpraslojdfdaaesfpllhnihselidejrgrfmmaldfnrejophlanehrdsjrrsidomemhmeafrgrrajrrfrjjgpfmgsprifnolfglhmnfapljamsldgrfsomopfedsegdadmojparrssjpfsfaporljfhsfhhgrnilmhdlppoldhaomrjprnfirlmnnhfseofjenrohflfndfiimmsirjopeeipafhphogsafrngjjiprnifeila...
output:
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooonnmllkjjiihhggfedcbbba
result:
wrong answer 1st lines differ - expected: 'oooooooooooooooooooooooooooooo...oooooooonnmllkjjiihhggfedcbbbba', found: 'oooooooooooooooooooooooooooooo...ooooooooonnmllkjjiihhggfedcbbba'