Submission #821484

#	Time	Username	Problem	Language	Result	Execution time	Memory
821484		devariaota	Ekoeko (COCI21_ekoeko)	C++17	10 / 110	4 ms	724 KiB

Main

#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(ll 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 < 2*n ; j++){
      d2[s[j]-'a'] = min(d2[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<<s<<endl;
  }
  cout<<ans<<"\n";
}

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

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40