QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#675054 | #7175. Mixed Messages | Rezhou# | AC ✓ | 13ms | 20568kb | C++23 | 3.8kb | 2024-10-25 17:53:43 | 2024-10-25 17:53:43 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;
typedef pair<int, pair<int, int>> pip;
typedef const double* (*p_fun)(const double*, int);
const LL N = 2e5 + 10, M = 2e3 + 10, mod = 1e9 + 7, LLF = 1e15,
null = 0x3f3f3f3f3f3f3f;
template <typename T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T, typename... Args>
bool chmax(T& a, const T& b, const Args &...args) {
bool updated = chmax(a, b);
return chmax(a, args...) || updated;
}
template <typename T>
bool chmin(T& a, const T& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T, typename... Args>
bool chmin(T& a, const T& b, const Args &...args) {
bool updated = chmin(a, b);
return chmin(a, args...) || updated;
}
class UnionFind {
public:
vector<int> parent;
vector<int> size;
int n;
// 当前连通分量数目
int setCount;
public:
UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
bool connected(int x, int y) {
x = find(x);
y = find(y);
return x == y;
}
};
int qmi(int a, int b) {
int res = 1;
a %= mod;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int sqrt(int x) {
int l = 0, r = 3e9; // LLONG_MAX
while (l < r) {
int mid = (l + r + 1) >> 1;
if (mid * mid > x)
r = mid - 1; // 向下取整
else
l = mid;
}
return r;
}
bool isrun(int x) {
if (x % 400 == 0 || (x % 4 == 0 && (x % 100 != 0))) return 1;
return 0;
}
int yue[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
static inline void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = ' ' + s;
vector<vector<int>> f(n + 1, vector<int>(6)), f2(n + 1, vector<int>(6));
vector<int> now(6);
fill(now.begin(), now.end(), -LLF);
map<char, int> mp;
string ss = " spbsu";
mp['s'] = 1, mp['p'] = 2, mp['b'] = 3, mp['u'] = 4;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 4; j++) {
f[i][j] = now[j];
}
now[mp[s[i]]] = i;
}
fill(now.begin(), now.end(), LLF);
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= 4; j++) {
f2[i][j] = now[j];
}
now[mp[s[i]]] = i;
}
int all = LLF;
for (int i = 1; i <= n; i++) {
if (s[i] == 'b') {
int ans = 0;
if (f[i][2] == -LLF) continue;
ans += i - f[i][2] - 1;
int pos = f[i][2];
if (f[pos][1] == -LLF) continue;
ans += i - f[pos][1] - 2;
if (f2[i][1] == LLF) continue;
ans += f2[i][1] - i - 1;
pos = f2[i][1];
if (f2[pos][4] == LLF) continue;
ans += f2[pos][4] - i - 2;
chmin(all, ans);
}
}
cout << all;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << unitbuf;
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
6 spbssu
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
15 spongebaseurban
output:
11
result:
ok answer is '11'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
5 spbsu
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
6 sppbsu
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
13 spbpbsaaaaaau
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
100 supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups
output:
4
result:
ok answer is '4'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
100 nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt
output:
61
result:
ok answer is '61'
Test #8:
score: 0
Accepted
time: 11ms
memory: 20256kb
input:
100000 supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 10ms
memory: 20512kb
input:
100000 nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...
output:
5
result:
ok answer is '5'
Test #10:
score: 0
Accepted
time: 8ms
memory: 20364kb
input:
100000 sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 4ms
memory: 20328kb
input:
100000 spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
99995
result:
ok answer is '99995'
Test #12:
score: 0
Accepted
time: 9ms
memory: 20360kb
input:
100000 spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
199990
result:
ok answer is '199990'
Test #13:
score: 0
Accepted
time: 10ms
memory: 20568kb
input:
100000 spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
99995
result:
ok answer is '99995'
Test #14:
score: 0
Accepted
time: 6ms
memory: 20328kb
input:
100000 spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...
output:
0
result:
ok answer is '0'
Test #15:
score: 0
Accepted
time: 8ms
memory: 20256kb
input:
100000 sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
79996
result:
ok answer is '79996'
Test #16:
score: 0
Accepted
time: 9ms
memory: 20304kb
input:
100000 spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...
output:
6
result:
ok answer is '6'
Test #17:
score: 0
Accepted
time: 9ms
memory: 20368kb
input:
100000 spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...
output:
0
result:
ok answer is '0'
Test #18:
score: 0
Accepted
time: 9ms
memory: 20496kb
input:
100000 spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...
output:
2
result:
ok answer is '2'
Test #19:
score: 0
Accepted
time: 6ms
memory: 20356kb
input:
100000 aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...
output:
0
result:
ok answer is '0'
Test #20:
score: 0
Accepted
time: 13ms
memory: 20524kb
input:
100000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
ok answer is '0'
Extra Test:
score: 0
Extra Test Passed