QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165773#7175. Mixed Messagesucup-team368#AC ✓3ms5112kbC++202.4kb2023-09-05 21:37:222023-09-05 21:37:23

Judging History

This is the latest submission verdict.

  • [2023-09-05 21:37:23]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 5112kb
  • [2023-09-05 21:37:22]
  • Submitted

answer

#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

void solve() {
    int N; cin >> N;
    string S; cin >> S;
    
    vector<int> lst(N, -1), nxt(N, N);
    for (int i = 0, s = -1, p = -1; i < N; ++i) {
        if (S[i] == 's') s = i;
        if (S[i] == 'p') p = i, lst[i] = s;
        if (S[i] == 'b') lst[i] = p;
    }
    for (int i = N-1, u = N, s = N; i >= 0; --i) {
        if (S[i] == 'u') u = i;
        if (S[i] == 's') s = i, nxt[i] = u;
        if (S[i] == 'b') nxt[i] = s;
    }
    
    int ans = N * N;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'b' and lst[i] != -1 and lst[lst[i]] != -1 and nxt[i] != N and nxt[nxt[i]] != N) {
            // debug(lst[lst[i]], lst[i], i, nxt[i], nxt[nxt[i]]);
            chmin(ans, (i - lst[lst[i]] - 2) + (i - lst[i] - 1) + (nxt[i] - i - 1) + (nxt[nxt[i]] - i - 2));
        }
    }
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FILE__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

#endif

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3508kb

input:

6
spbssu

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

15
spongebaseurban

output:

11

result:

ok answer is '11'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

5
spbsu

output:

0

result:

ok answer is '0'

Test #4:

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

input:

6
sppbsu

output:

1

result:

ok answer is '1'

Test #5:

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

input:

13
spbpbsaaaaaau

output:

8

result:

ok answer is '8'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

100
supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups

output:

4

result:

ok answer is '4'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

100
nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt

output:

61

result:

ok answer is '61'

Test #8:

score: 0
Accepted
time: 1ms
memory: 5048kb

input:

100000
supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 2ms
memory: 4884kb

input:

100000
nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...

output:

5

result:

ok answer is '5'

Test #10:

score: 0
Accepted
time: 2ms
memory: 4968kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4928kb

input:

100000
spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

99995

result:

ok answer is '99995'

Test #12:

score: 0
Accepted
time: 2ms
memory: 4924kb

input:

100000
spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

199990

result:

ok answer is '199990'

Test #13:

score: 0
Accepted
time: 2ms
memory: 5112kb

input:

100000
spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

99995

result:

ok answer is '99995'

Test #14:

score: 0
Accepted
time: 2ms
memory: 4964kb

input:

100000
spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

0

result:

ok answer is '0'

Test #15:

score: 0
Accepted
time: 2ms
memory: 5048kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

79996

result:

ok answer is '79996'

Test #16:

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

input:

100000
spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...

output:

6

result:

ok answer is '6'

Test #17:

score: 0
Accepted
time: 2ms
memory: 4896kb

input:

100000
spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...

output:

0

result:

ok answer is '0'

Test #18:

score: 0
Accepted
time: 2ms
memory: 4888kb

input:

100000
spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 3ms
memory: 4936kb

input:

100000
aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4984kb

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Extra Test:

score: 0
Extra Test Passed