QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#169490 | #7175. Mixed Messages | ucup-team198# | AC ✓ | 5ms | 7872kb | C++23 | 1.6kb | 2023-09-09 13:33:02 | 2023-09-09 13:33:04 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define endl '\n'
using LL=long long;
const string pat="spbsu";
constexpr int N = 1e5 + 10;
int n,pre[N][5],nxt[N][5];
void solve() {
cin>>n;
string s;
cin>>s;
for(int i=1; i<=n; ++i) {
for(int j=0; j<5; ++j) {
pre[i][j]=pre[i-1][j];
if(pat[j]==s[i-1])
pre[i][j]=i;
}
}
for(int j=0; j<5; ++j)
nxt[n+1][j]=n+1;
for(int i=n; i>=1; --i) {
for(int j=0; j<5; ++j) {
nxt[i][j]=nxt[i+1][j];
if(pat[j]==s[i-1])
nxt[i][j]=i;
}
}
int ans=1e9;
for(int i=1; i<=n; ++i) {
for(int j=0; j<5; ++j) {
if(pat[j]==s[i-1]) {
int cur=0;
int p=i, id=j;
while(id>0) {
int p2=pre[p][id-1];
if(p2==0) {
cur=1e9;
break;
}
cur+=(p-p2-1)*id;
p=p2, id--;
}
p=i, id=j;
while(id<4) {
int p2=nxt[p][id+1];
if(p2==n+1) {
cur=1e9;
break;
}
cur+=(p2-p-1)*(4-id);
p=p2, id++;
}
ans=min(ans,cur);
}
}
}
cout<<ans<<"\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
6 spbssu
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
15 spongebaseurban
output:
11
result:
ok answer is '11'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 spbsu
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6 sppbsu
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
13 spbpbsaaaaaau
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
100 supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups
output:
4
result:
ok answer is '4'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
100 nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt
output:
61
result:
ok answer is '61'
Test #8:
score: 0
Accepted
time: 5ms
memory: 7596kb
input:
100000 supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7840kb
input:
100000 nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...
output:
5
result:
ok answer is '5'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7616kb
input:
100000 sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7640kb
input:
100000 spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
99995
result:
ok answer is '99995'
Test #12:
score: 0
Accepted
time: 4ms
memory: 7584kb
input:
100000 spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
199990
result:
ok answer is '199990'
Test #13:
score: 0
Accepted
time: 4ms
memory: 7872kb
input:
100000 spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
99995
result:
ok answer is '99995'
Test #14:
score: 0
Accepted
time: 0ms
memory: 7652kb
input:
100000 spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...
output:
0
result:
ok answer is '0'
Test #15:
score: 0
Accepted
time: 1ms
memory: 7656kb
input:
100000 sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
79996
result:
ok answer is '79996'
Test #16:
score: 0
Accepted
time: 1ms
memory: 7640kb
input:
100000 spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...
output:
6
result:
ok answer is '6'
Test #17:
score: 0
Accepted
time: 1ms
memory: 7872kb
input:
100000 spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...
output:
0
result:
ok answer is '0'
Test #18:
score: 0
Accepted
time: 1ms
memory: 7648kb
input:
100000 spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...
output:
2
result:
ok answer is '2'
Test #19:
score: 0
Accepted
time: 5ms
memory: 7644kb
input:
100000 aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...
output:
0
result:
ok answer is '0'
Test #20:
score: 0
Accepted
time: 1ms
memory: 7872kb
input:
100000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
ok answer is '0'
Extra Test:
score: 0
Extra Test Passed