Submission #1197191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197191		Joon_Yorigami	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	16000 KiB

dna

/*
                                                                   .:-=++***#***+=:.
                                                       .:-==+**##**%########***#####*=:.
                                                   .-+#%%#*****############**#******#####+=:
                                                .-*%#####********###########*********#######*+-:
                                              :+#######**********########*****+********##########+-.
                                            :+##########**###******##********************###########+:
                                          :+##########*****#*******###**********************###***####*:
                                        .=###########***###*******#***************************#****#####*:
                                       :*#################******************************************######=
                                      -###################***************+****************************#####*:
                                    .=###################******************************************#****#####+.
                                   :*###################*******************************+************#*****#####:
                                  =#############**######*****#*******************++***++++++***************#####=
                                .*###########******####*****#************+++*+**+++***++++++++***#**********#####+
                               -############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####*
                              =############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*.
                            .+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*.
                           .*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*.
               .:-:       .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*.
           .--:++=+.     .**.  ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*:
           :++=====     .**.  -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=:
            .-=++=      =*.   +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+:
                .      .#.   .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+:
                       --    -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-.
         -=+++-.       =     +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=:
       .++====++       =     ####################**##*****###***#+****#=#****  .+*###************+  ##   +***######****##########+--+#%%%%+:
  .---:=+======+:      +.    ##################%#***#*****####****#**#+-####.  .+###***##*******#  .#:   :***########***##%%%####%#=. .:=*%%
 ---==++=======+=      -=   .%#################%****#*****######-#*##*.=%#*.    +=---:::.......:   =:     =**#########***#%%%%%%%%%%%=.   .-
 :-:===========+=      .#.  :%################%%****#*****#####= :-+***#*=.                               .*#########%%#**#*=%%%%%%%%%%=.
  .---=========+=       :*. -#################%%****#*****%#+-.-*#%%%@###*=                                +##########%%%***:+-#%%%#####*:
    .:=++++====+-        =*.=###%############%@%****#*****#. =###%%%@@@+                                   ###########%%%%#*#:  -*########=
        ..:::::-.         +*+###%####%######%%+******#****#=##= -@@@@@@@+                                 =*###########%%%%##+    :*#######+
                           =%##+%####%######%+.******#*****%%#-:+@@@@%-=*                                 +..###########%##%%%*.    -#######
                            %##=#####%###%%#%:=******#*****%*.**##*+=:  .                   -+**####*=:  -  .=###############%%*:    .+#####
                           .%###%########%%%%:.#*****##*****= .+:      .                   :-::.:--=++-  :  .-*##################+:    :####
                           :##.*###########%@# #************+   .:.-==--                                .    +**###+*##############*:   .*##
                           -%- ############%@@-#*###*#=##***#.                                          :.  =*++*#**++*##############*-  .##
                           =#  ############@@@######*#:###*##=                                          :..+*++++***+++++*##############=.+#
                           +:  ###########%@%%%%######.=######                                         .=+#+++++++***+++++****##############
                          .+   *##########%%%%%%######::######=                                        =+++#*+++++++*#+++++******###########
                          +:   =%#%######%%%##%@######:-+######.              .:------==              :*++++**+++++++*#*+++++********#######
                         -*    :%%%%#####%%%##%%%#####***######*             -=--------=:            -*+++++++*++++++++*#**+++*=:=******+==*
                        .*+     +%%%%###%%####%%%#####**+#######=            -........:=:          -++++++++++*#**##***+******++- .-******=.
                        -*=      *%%%%##%%%%%%%#%#####**++#######.           :.........-        .=#%%%######%##########%#+*******.  .-++++*+
                        -*+     .*%%%%#%%#######%#####*++++######*:           .........      :=#%@@%%%%%%#################*++*****=.  .-++++
                        :**.   :###%%%#%%########%####*++++*#######=-:..                  -+#%%%###########################++++****#=.  .-++
                         -*+  .######%%%%#########%###@@@%%%%######+...:----:.         :*%################################%*+++++*+###-   .+
                          :*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+.  .
                            -+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*.  =##+
                             +#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++    -##.
                            =%**********#######%%###############%*#####=...=.        .  :-=-: .###############%#******####%#####+=     +*
                            *#************#############%%#######**+*%####-.-                .-:=##############%*********##%#######=:  .+.
                            *#****************##**######%%%###*:   ::*#####:     -::            .-+####%%%####%*********#%##########*-:
                            =#***********************######%*-        .--:=:.   =. :--:             .-=*###%###*********#######*#######+-
                            .#**************************###=             .:.  ::...   .=.               +***#%##*******#########***#######+:
                             =##**************************:      :-:--.  .. .+.....     +               =******#%#####%##########***#####**#
                              ####**********************+.    . :#########+-=:....      -:              +***********##%%#***######****##****
                              .#%####******************-        *##########*:....... ...:.              #**************##*********###*##****
                               :#%@%%%###*************          =#*******####+....... :-.              *#***************%************#%#****
                              .#**###%%%%%######****#.           =#***********#=....:-.              :*#****************##*************####*
                              *#**#****#####%%%%#####             =#*************+=:       .=-::..:-*#*****************##*****************##
                             -#***#*******######%%%%=               :=*#**********:    ...  ##*##%##*******************#********************
                            .%*****#*********######%.                    ....:-=*-  :++:   =#****##%####*************###********************
:.                          +#*****#**********####%+                            ..-*#***#+=##*******##%%###********####*********************
 .:-:.                     .%#*****#**********#%%%*                  :=+**##########******###********#%%%%%%##****###***********************
     --                    =%#******#*********@#%%-.               :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####*************************
=-.   .=.                  ##*******#********#%#**###*+=-:.:     -######%##%###%####%%%%%##########%####%%%%##%*************####************
====   .=                 :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####***********
 ====   -:                *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####**********
 :+=+.   =               .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######*********
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
cheese;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using mll = map<ll, ll>;
using sll = set<ll>;
using sc = set<char>;
#define printv(v) {for(auto &elem:v){cout<<elem<<" ";}cout<<endl;}
#define printg(g) {for(auto &row:g){printv(row)};}
#define printm(m) {for(auto &pa:m){cout << pa.first << "," << pa.second << " ";};cout<<endl;}
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool is_prime(ll a)
{
    if(a==1) return false;
    for(ll i=2;i*i<=a;i++)
    {
        if (a%i==0) return false;
    }
    return true;
}
ll binpow(ll a, ll b, ll m)
{
    a %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll moddiv(ll numerator,ll denominator, ll mod)
{
    numerator %= mod;
    denominator %= mod;
    return numerator * binpow(denominator,mod-2,mod) % mod;
}

//DSU https://cp-algorithms.com/data_structures/disjoint_set_union.html
const int DSUN = 200000;

int parent[DSUN];
int set_size[DSUN];

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void make_set(int v) {
    parent[v] = v;
    set_size[v] = 1;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (set_size[a] < set_size[b])
            swap(a, b);
        parent[b] = a;
        set_size[a] += set_size[b];
    }
}

//DSU

//https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
vector<char> segmentedSieve(ll L, ll R) {
    // generate all primes up to sqrt(R)
    ll lim = sqrt(R);
    vector<char> mark(lim + 1, false);
    vector<ll> primes;
    for (ll i = 2; i <= lim; ++i) {
        if (!mark[i]) {
            primes.emplace_back(i);
            for (ll j = i * i; j <= lim; j += i)
                mark[j] = true;
        }
    }

    vector<char> isPrime(R - L + 1, true);
    for (ll i : primes)
        for (ll j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
            isPrime[j - L] = false;
    if (L == 1)
        isPrime[0] = false;
    return isPrime;
}

//segtree

vector<ll> builder(vector<ll> &arr)
{
    ll identityelement = 0;
    vector<ll> segtree;
    ll n,segtree_size;
    n=arr.size();
    segtree_size=1;
    while(segtree_size<n)
    {
      segtree_size<<=1;
    }
    segtree.assign(2*segtree_size,0);
    for(int i=0;i<n;i++)
    {
      segtree[segtree_size+i]=arr[i];
    }
    for(int i=segtree_size-1;i>0;i--)
    {
      segtree[i]=segtree[i*2]+segtree[i*2+1];
    }
    return segtree;
}

ll query_sum(vector<ll>&segtree,vector<ll>&lazy,ll query_l,ll query_r,ll val,ll node_l,ll node_r,ll node)
{
  if(lazy[node]!=0)
  {
    segtree[node]+=(node_r-node_l+1)*lazy[node];
    if(node_l!=node_r)
    {
      lazy[node*2]+=lazy[node];
      lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
  }
  if(val!=-1 && query_l<=node_l && node_r<=query_r)
  {
    segtree[node]+=(node_r-node_l+1)*val;
    if(node_l!=node_r)
    {
      lazy[node*2]+=val;
      lazy[node*2+1]+=val;
    }
    lazy[node]=0;
  }
  if(query_l<=node_l && node_r<=query_r)
  {
    return segtree[node];
  }
  else if(node_r<query_l || query_r<node_l)
  {
    return 0ll;
  }
  else
  {
    ll mid = node_l+(node_r-node_l)/2;
    ll sum = query_sum(segtree,lazy,query_l,query_r,val,node_l,mid,node*2)+query_sum(segtree,lazy,query_l,query_r,val,mid+1,node_r,node*2+1);
    segtree[node] = segtree[node*2]+segtree[node*2+1];
    return sum;
  }
  return 0ll;
}

//segtree

vector<pll> vals;

ll s(ll x)
{
  ll ret,n;
  n=x;
  ret=0;
  while(n>0)
  {
    ret+=n%10;
    n/=10;
  }
  return ret;
}

ll S(ll k,ll x)
{
  if(k==0)
  {
    return x;
  }
  else
  {
    return s(S(k-1,x));
  }
}

ll f(ll k,ll x)
{
  ll total;
  vll owo;
  if(k==1){return x+s(x);}
  owo.push_back(x);
  for(int i=0;i<6;i++)
  {
    owo.push_back(s(owo.back()));
  }
  total=0;
  for(int i=0;i<=min(k,5);i++)
  {
    total+=owo[i];
  }
  if(k>5)
  {
    total+=(k-5)*owo[6];
  }
  return total;
}

ll kadane(vll &a)
{
  ll ans = a[0], sum = 0;

  for (int r = 0; r < a.size(); r++)
  {
      sum += a[r];
      ans = max(ans, sum);
      sum = max(sum, 0);
  }
  return ans;
}

vector<bool>sieve(ll n)
{
  vector<bool>ret(n+1,true);
  ret[0]=false;
  ret[1]=false;
  for(ll i=2;i<=n;i++)
  {
    if(ret[i])
    {
      for(ll j=i*i;j<=n;j+=i)
      {
        ret[j]=false;
      }
    }
  }
  return ret;
}

ll MAX_N=100000;
vector<vll> cntA(3,vll(MAX_N+1,0));
vector<vll> cntB(3,vll(MAX_N+1,0));
vector<vector<vll>> swaps(3,vector<vll>(3,vll(MAX_N+1,0)));
void init(string a, string b)
{
  ll owo;
  for(int i=0;i<a.size();i++)
  {
    cntA[0][i+1]=cntA[0][i];
    cntA[1][i+1]=cntA[1][i];
    cntA[2][i+1]=cntA[2][i];
    if(a[i]=='A')
    {
      cntA[0][i+1]+=1;
    }
    else if(a[i]=='C')
    {
      cntA[1][i+1]+=1;
    }
    else
    {
      cntA[2][i+1]+=1;
    }
  }

  for(int i=0;i<b.size();i++)
  {
    cntB[0][i+1]=cntB[0][i];
    cntB[1][i+1]=cntB[1][i];
    cntB[2][i+1]=cntB[2][i];
    if(b[i]=='A')
    {
      cntB[0][i+1]+=1;
    }
    else if(b[i]=='C')
    {
      cntB[1][i+1]+=1;
    }
    else
    {
      cntB[2][i+1]+=1;
    }
  }

  for(int i=0;i<a.size();i++)
  {
    swaps[0][0][i+1]=swaps[0][0][i];
    swaps[0][1][i+1]=swaps[0][1][i];
    swaps[0][2][i+1]=swaps[0][2][i];
    swaps[1][0][i+1]=swaps[1][0][i];
    swaps[1][1][i+1]=swaps[1][1][i];
    swaps[1][2][i+1]=swaps[1][2][i];
    swaps[2][0][i+1]=swaps[2][0][i];
    swaps[2][1][i+1]=swaps[2][1][i];
    swaps[2][2][i+1]=swaps[2][2][i];
    if(a[i]=='A')
    {
      if(b[i]=='A')
      {
        swaps[0][0][i+1]+=1;
      }
      else if(b[i]=='C')
      {
        swaps[0][1][i+1]+=1;
      }
      else
      {
        swaps[0][2][i+1]+=1;
      }
    }
    else if(a[i]=='C')
    {
      if(b[i]=='A')
      {
        swaps[1][0][i+1]+=1;
      }
      else if(b[i]=='C')
      {
        swaps[1][1][i+1]+=1;
      }
      else
      {
        swaps[1][2][i+1]+=1;
      }
    }
    else
    {
      if(b[i]=='A')
      {
        swaps[2][0][i+1]+=1;
      }
      else if(b[i]=='C')
      {
        swaps[2][1][i+1]+=1;
      }
      else
      {
        swaps[2][2][i+1]+=1;
      }
    }
  }
}

/*
A -> 0
C -> 1
T -> 2
*/

int get_distance(int x, int y)
{
  x+=1;
  y+=1;
  bool check=true;
  for(int i=0;i<3;i++)
  {
    check&=(cntA[i][y]-cntA[i][x-1]==cntB[i][y]-cntB[i][x-1]);
  }
  if(!check) return -1;
  ll ans=0,temp=0;
  ans+=min((swaps[0][1][y]-swaps[0][1][x-1]),(swaps[1][0][y]-swaps[1][0][x-1]));
  ans+=min((swaps[2][1][y]-swaps[2][1][x-1]),(swaps[1][2][y]-swaps[1][2][x-1]));
  ans+=min((swaps[0][2][y]-swaps[0][2][x-1]),(swaps[2][0][y]-swaps[2][0][x-1]));
  temp+=abs((swaps[0][1][y]-swaps[0][1][x-1])-(swaps[1][0][y]-swaps[1][0][x-1]));
  temp+=abs((swaps[2][1][y]-swaps[2][1][x-1])-(swaps[1][2][y]-swaps[1][2][x-1]));
  temp+=abs((swaps[0][2][y]-swaps[0][2][x-1])-(swaps[2][0][y]-swaps[2][0][x-1]));
  ans+=temp/3*2;
  return ans;
}
/*
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  vll segtree,lazy;
  ll segtree_size;
  segtree=builder(arr);
  segtree_size=segtree.size()/2;
  lazy.assign(segtree_size*2,0);
  update: query_sum(segtree,lazy,a,b,c,1,segtree_size,1);
  query: cout << query_sum(segtree,lazy,a,b,-1,1,segtree_size,1) << endl;
  ll n,q,l,r;
  string a,b;
  cin >> n >> q;
  cin >> a;
  cin >> b;
  init(a,b);
  while(q--)
  {
    cin >> l >> r;
    cout << get_distance(l,r) << endl;
  }
}
*/

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16