oj.uz

Submission #821477

# Submission time Handle Problem Language Result Execution time Memory
821477 2023-08-11T10:41:34 Z kebine Ekoeko (COCI21_ekoeko) C++17
10 / 110
 3 ms 852 KB 
#include <bits/stdc++.h>
#define ll long long
#define longlonginf LONG_LONG_MAX
#define inf INT_MAX
using namespace std;

ll n,m,x;
ll l,r;
string s;

bool subtask1(){
  for(int i = 0 ; i < n ; i++) if( s[i] != 'a' ) return 0;
  for(int i = n ; i < 2*n ; i++) if( s[i] != 'b' ) return 0;
  return 1;
}

void solve(){
  cin>>n;
  cin>>s;
  //subtask 1
  if( subtask1() ){
    n /= 2;
    cout<<n*n<<"\n";
    return;
  }
  //~ n *= 2;
  //~ vector<vector<ll>> pos;
  //~ for(int i = 0 ; i < n ; i++){
    //~ pos[s[i]-'a'].push_back(i);
  //~ }
  //~ bool done[26];
  //~ memset(done,0,sizeof(done));
  //~ ll dist;
  //~ char foo;
  //~ for(int i = 0 ; i < n/2 ; i++){
    //~ dist = longlonginf;
    //~ for(int j = 0 ; j < 26 ; j++){
      //~ if( pos[j].empty() || done[j] ) continue;
      //~ ll x = min(abs(i-pos[j][0])+abs(n+i-pos[j][1]),abs(i-pos[j][1])+abs(n+i-pos[j][0])); 
      //~ if( dist > x ){
        //~ dist = x;
        //~ foo = 'a'+j;
      //~ }
    //~ }
  //~ }
  ll ans = 0;
  for(int i = 0 ; i < n ; i++){
    ll mn = inf;
    ll d1[26],d2[26];
    for(int j = 0 ; j < 26 ; j++) d1[j] = d2[j] = inf;
    for(ll j = i ; j < n ; j++){
      d1[s[j]-'a'] = min(d1[s[j]-'a'],j);
    }
    for(ll j = n+i ; j < n ; j++){
      d2[s[j]-'a'] = min(d1[s[j]-'a'],j);
    }
    ll t1,t2;
    for(int j = 0 ; j < 26 ; j++){
      if( mn > abs(d1[j]-i) + abs(d2[j]-(n+i)) ){
        mn = abs(d1[j]-i) + abs(d2[j]-(n+i));
        t1 = d1[j];
        t2 = d2[j];
      }
      ans += mn;
      while( t1 != i ){
        swap(s[t1],s[t1-1]);
        t1--;
      }
      while( t2 != n+i ){
        swap(s[t2],s[t2-1]);
        t2--;
      }
    }
    cout<<ans<<"\n";
  }
}

int main(){
  int T = 1;
  //cin>>T;
  for(int i = 1 ; i <= T ; i++){
    solve();
  }
  return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:69:17: warning: 't2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |       while( t2 != n+i ){
      |              ~~~^~~~~~
Main.cpp:65:17: warning: 't1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |       while( t1 != i ){
      |              ~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Runtime error 1 ms 340 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Runtime error 1 ms 352 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Runtime error 1 ms 340 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -