QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318916#7175. Mixed MessagesPhanDinhKhoi#AC ✓15ms50872kbC++202.4kb2024-02-01 10:55:452024-02-01 10:55:45

Judging History

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

  • [2024-02-01 10:55:45]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:50872kb
  • [2024-02-01 10:55:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<ld,ld> pld;

#define fi first
#define se second
#define pb push_back

#define rep(i,a,b) for (int i=int(a);i < int(b);i++)

#define ffor(i,n) for (int i=0;i <int(n);i++)  
#define sz(x) ((int) (x).size()) 
#define all(x) x.begin(),x.end()




ll nxt[100005][30];
ll pre[100005][30];


int main() {  
    ios_base::sync_with_stdio(false);  cin.tie(NULL);
  
    ll n ; cin >> n;
    string s ; cin >> s;

    for (int i = 0 ; i <= n ; i++) {
      for (int j = 0 ; j < 26 ; j++) {
        nxt[i][j] = n;
        pre[i][j] = -1;
      }
    }

    for (int i = n-1; i >= 0 ; i--) {
      for (int j = 0 ; j < 26 ; j++) {
        nxt[i][j] = nxt[i+1][j];
      }
      int id = int(s[i]-'a');
      nxt[i][id] = i;
    }

    for (int i = 0 ; i <= n-1 ; i++) {
        if (i > 0) {

            for (int j = 0 ; j < 26 ; j++) {
               pre[i][j] = pre[i-1][j];
            }

        }
    
        
        int id = int(s[i]-'a');
        pre[i][id] = i;
    }
    
    ll res = 1e18;
    for (int i = 2 ; i+2 < n ; i++) {
        if (s[i] == 'b') {
        //  cout << "AT : " << i << '\n';
            ll cost = 0;

            int id1 = int('p' - 'a');
            int id2 = int('s' - 'a');
            
            int p1 = pre[i-1][id1];
            if (p1 <= 0) continue;

           // cout << "P1 : " << p1 << '\n';
            ll len1 = i - p1 - 1; 
            cost += len1*2;
            
            int p2 = pre[p1-1][id2];
           //  cout << "P2 : " << p2 << '\n';
            if (p2 < 0) continue;
            ll len2 = p1 - p2 - 1;
            cost += len2;


            id1 = int('s' - 'a');
            id2 = int('u' - 'a');

            p1 = nxt[i+1][id1];
           // cout << "N1 : " << p1 << '\n';
            if (p1+1 >= n) continue;
             len1 = p1 - i - 1; 
            cost += len1*2;

            p2 = nxt[p1+1][id2];
          //  cout << "N2 : " << p2 << '\n';
            if (p2 >= n) continue;
             len2 = p2 - p1 - 1;
            cost += len2;


           // cout << "COST : " << cost << '\n';
            res = min(res,cost);
        }
    }
    cout << res << '\n';
    

      





  
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
spbssu

output:

1

result:

ok answer is '1'

Test #2:

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

input:

15
spongebaseurban

output:

11

result:

ok answer is '11'

Test #3:

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

input:

5
spbsu

output:

0

result:

ok answer is '0'

Test #4:

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

input:

6
sppbsu

output:

1

result:

ok answer is '1'

Test #5:

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

input:

13
spbpbsaaaaaau

output:

8

result:

ok answer is '8'

Test #6:

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

input:

100
supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups

output:

4

result:

ok answer is '4'

Test #7:

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

input:

100
nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt

output:

61

result:

ok answer is '61'

Test #8:

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

input:

100000
supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...

output:

0

result:

ok answer is '0'

Test #9:

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

input:

100000
nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...

output:

5

result:

ok answer is '5'

Test #10:

score: 0
Accepted
time: 14ms
memory: 50804kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

0

result:

ok answer is '0'

Test #11:

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

input:

100000
spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

99995

result:

ok answer is '99995'

Test #12:

score: 0
Accepted
time: 4ms
memory: 50668kb

input:

100000
spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

199990

result:

ok answer is '199990'

Test #13:

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

input:

100000
spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

99995

result:

ok answer is '99995'

Test #14:

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

input:

100000
spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

0

result:

ok answer is '0'

Test #15:

score: 0
Accepted
time: 15ms
memory: 50568kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

79996

result:

ok answer is '79996'

Test #16:

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

input:

100000
spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...

output:

6

result:

ok answer is '6'

Test #17:

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

input:

100000
spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...

output:

0

result:

ok answer is '0'

Test #18:

score: 0
Accepted
time: 5ms
memory: 50644kb

input:

100000
spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 15ms
memory: 50676kb

input:

100000
aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...

output:

0

result:

ok answer is '0'

Test #20:

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

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Extra Test:

score: 0
Extra Test Passed