QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164993#7175. Mixed Messagesucup-team1056#AC ✓28ms52040kbC++201.6kb2023-09-05 15:16:572023-09-05 15:16:58

Judging History

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

  • [2023-09-05 15:16:58]
  • 评测
  • 测评结果:AC
  • 用时:28ms
  • 内存:52040kb
  • [2023-09-05 15:16:57]
  • 提交

answer

#include <bits/stdc++.h>
#define de(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define PII pair<int, int>
using LL = long long;
using namespace std;
constexpr int inf = 1e18;
constexpr int N = 1e6 + 10;
int n, m, k;
int a[N];

void solve(int Case) {
	cin >> n;
	string s; cin >> s;
	s = " " + s;
	vector ne1(n + 1, vector<int>(26)), ne2(n + 1, vector<int>(26));
	for (int i = 0; i < 26; i++) ne1[n][i] = ne2[1][i] = inf;
	for (int i = n - 1; i >= 0; i--) {
        ne1[i] = ne1[i + 1];
        ne1[i][s[i + 1] - 'a'] = i + 1;
    }
	for (int i = 2; i <= n; i++) {
        ne2[i] = ne2[i - 1];
        ne2[i][s[i - 1] - 'a'] = i - 1;
    }

    int ans = inf;
    int mid = (n - 1) / 2 + 1;
    for (int i = 1; i <= n; i++) {
    	if (s[i] == 'b') {
    		int p[5];
    		p[2] = i;
    		p[1] = ne2[p[2]]['p' - 'a'];
    		if (p[1] > inf - 10000) continue;
    		p[0] = ne2[p[1]]['s' - 'a'];
    		if (p[2] > inf - 10000) continue;
    		p[3] = ne1[p[2]]['s' - 'a'];
    		if (p[3] > inf - 10000) continue;
    		p[4] = ne1[p[3]]['u' - 'a'];
    		if (p[4] > inf - 10000) continue;

    		auto ds = [](int a, int b) {
    			return abs(a - b) - 1;
    		};
    		int res = ds(p[1], p[0]) + 2 * ds(p[2], p[1]) + 2 * ds(p[3], p[2]) + ds(p[4], p[3]);
    		ans = min(ans, res);
    	}
    }
    cout << ans;
}

signed main() {
	cin.tie(0)->ios::sync_with_stdio(false);

	int T = 1;
	// cin >> T; cin.get();

	int Case = 0;
	while (++Case <= T) {
		solve(Case);;
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3636kb

input:

6
spbssu

output:

1

result:

ok answer is '1'

Test #2:

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

input:

15
spongebaseurban

output:

11

result:

ok answer is '11'

Test #3:

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

input:

5
spbsu

output:

0

result:

ok answer is '0'

Test #4:

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

input:

6
sppbsu

output:

1

result:

ok answer is '1'

Test #5:

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

input:

13
spbpbsaaaaaau

output:

8

result:

ok answer is '8'

Test #6:

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

input:

100
supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups

output:

4

result:

ok answer is '4'

Test #7:

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

input:

100
nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt

output:

61

result:

ok answer is '61'

Test #8:

score: 0
Accepted
time: 23ms
memory: 51768kb

input:

100000
supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 8ms
memory: 51764kb

input:

100000
nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...

output:

5

result:

ok answer is '5'

Test #10:

score: 0
Accepted
time: 7ms
memory: 51844kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 13ms
memory: 51776kb

input:

100000
spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

99995

result:

ok answer is '99995'

Test #12:

score: 0
Accepted
time: 10ms
memory: 51832kb

input:

100000
spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

199990

result:

ok answer is '199990'

Test #13:

score: 0
Accepted
time: 18ms
memory: 51860kb

input:

100000
spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

99995

result:

ok answer is '99995'

Test #14:

score: 0
Accepted
time: 8ms
memory: 51928kb

input:

100000
spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

0

result:

ok answer is '0'

Test #15:

score: 0
Accepted
time: 8ms
memory: 51796kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

79996

result:

ok answer is '79996'

Test #16:

score: 0
Accepted
time: 28ms
memory: 52040kb

input:

100000
spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...

output:

6

result:

ok answer is '6'

Test #17:

score: 0
Accepted
time: 9ms
memory: 51984kb

input:

100000
spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...

output:

0

result:

ok answer is '0'

Test #18:

score: 0
Accepted
time: 13ms
memory: 51852kb

input:

100000
spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 22ms
memory: 51788kb

input:

100000
aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 17ms
memory: 51832kb

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Extra Test:

score: 0
Extra Test Passed