제출 #1218184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218184		Joon_Yorigami	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	26804 KiB

shoes

/*
                                                                   .:-=++***#***+=:.
                                                       .:-==+**##**%########***#####*=:.
                                                   .-+#%%#*****############**#******#####+=:
                                                .-*%#####********###########*********#######*+-:
                                              :+#######**********########*****+********##########+-.
                                            :+##########**###******##********************###########+:
                                          :+##########*****#*******###**********************###***####*:
                                        .=###########***###*******#***************************#****#####*:
                                       :*#################******************************************######=
                                      -###################***************+****************************#####*:
                                    .=###################******************************************#****#####+.
                                   :*###################*******************************+************#*****#####:
                                  =#############**######*****#*******************++***++++++***************#####=
                                .*###########******####*****#************+++*+**+++***++++++++***#**********#####+
                               -############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####*
                              =############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*.
                            .+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*.
                           .*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*.
               .:-:       .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*.
           .--:++=+.     .**.  ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*:
           :++=====     .**.  -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=:
            .-=++=      =*.   +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+:
                .      .#.   .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+:
                       --    -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-.
         -=+++-.       =     +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=:
       .++====++       =     ####################**##*****###***#+****#=#****  .+*###************+  ##   +***######****##########+--+#%%%%+:
  .---:=+======+:      +.    ##################%#***#*****####****#**#+-####.  .+###***##*******#  .#:   :***########***##%%%####%#=. .:=*%%
 ---==++=======+=      -=   .%#################%****#*****######-#*##*.=%#*.    +=---:::.......:   =:     =**#########***#%%%%%%%%%%%=.   .-
 :-:===========+=      .#.  :%################%%****#*****#####= :-+***#*=.                               .*#########%%#**#*=%%%%%%%%%%=.
  .---=========+=       :*. -#################%%****#*****%#+-.-*#%%%@###*=                                +##########%%%***:+-#%%%#####*:
    .:=++++====+-        =*.=###%############%@%****#*****#. =###%%%@@@+                                   ###########%%%%#*#:  -*########=
        ..:::::-.         +*+###%####%######%%+******#****#=##= -@@@@@@@+                                 =*###########%%%%##+    :*#######+
                           =%##+%####%######%+.******#*****%%#-:+@@@@%-=*                                 +..###########%##%%%*.    -#######
                            %##=#####%###%%#%:=******#*****%*.**##*+=:  .                   -+**####*=:  -  .=###############%%*:    .+#####
                           .%###%########%%%%:.#*****##*****= .+:      .                   :-::.:--=++-  :  .-*##################+:    :####
                           :##.*###########%@# #************+   .:.-==--                                .    +**###+*##############*:   .*##
                           -%- ############%@@-#*###*#=##***#.                                          :.  =*++*#**++*##############*-  .##
                           =#  ############@@@######*#:###*##=                                          :..+*++++***+++++*##############=.+#
                           +:  ###########%@%%%%######.=######                                         .=+#+++++++***+++++****##############
                          .+   *##########%%%%%%######::######=                                        =+++#*+++++++*#+++++******###########
                          +:   =%#%######%%%##%@######:-+######.              .:------==              :*++++**+++++++*#*+++++********#######
                         -*    :%%%%#####%%%##%%%#####***######*             -=--------=:            -*+++++++*++++++++*#**+++*=:=******+==*
                        .*+     +%%%%###%%####%%%#####**+#######=            -........:=:          -++++++++++*#**##***+******++- .-******=.
                        -*=      *%%%%##%%%%%%%#%#####**++#######.           :.........-        .=#%%%######%##########%#+*******.  .-++++*+
                        -*+     .*%%%%#%%#######%#####*++++######*:           .........      :=#%@@%%%%%%#################*++*****=.  .-++++
                        :**.   :###%%%#%%########%####*++++*#######=-:..                  -+#%%%###########################++++****#=.  .-++
                         -*+  .######%%%%#########%###@@@%%%%######+...:----:.         :*%################################%*+++++*+###-   .+
                          :*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+.  .
                            -+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*.  =##+
                             +#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++    -##.
                            =%**********#######%%###############%*#####=...=.        .  :-=-: .###############%#******####%#####+=     +*
                            *#************#############%%#######**+*%####-.-                .-:=##############%*********##%#######=:  .+.
                            *#****************##**######%%%###*:   ::*#####:     -::            .-+####%%%####%*********#%##########*-:
                            =#***********************######%*-        .--:=:.   =. :--:             .-=*###%###*********#######*#######+-
                            .#**************************###=             .:.  ::...   .=.               +***#%##*******#########***#######+:
                             =##**************************:      :-:--.  .. .+.....     +               =******#%#####%##########***#####**#
                              ####**********************+.    . :#########+-=:....      -:              +***********##%%#***######****##****
                              .#%####******************-        *##########*:....... ...:.              #**************##*********###*##****
                               :#%@%%%###*************          =#*******####+....... :-.              *#***************%************#%#****
                              .#**###%%%%%######****#.           =#***********#=....:-.              :*#****************##*************####*
                              *#**#****#####%%%%#####             =#*************+=:       .=-::..:-*#*****************##*****************##
                             -#***#*******######%%%%=               :=*#**********:    ...  ##*##%##*******************#********************
                            .%*****#*********######%.                    ....:-=*-  :++:   =#****##%####*************###********************
:.                          +#*****#**********####%+                            ..-*#***#+=##*******##%%###********####*********************
 .:-:.                     .%#*****#**********#%%%*                  :=+**##########******###********#%%%%%%##****###***********************
     --                    =%#******#*********@#%%-.               :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####*************************
=-.   .=.                  ##*******#********#%#**###*+=-:.:     -######%##%###%####%%%%%##########%####%%%%##%*************####************
====   .=                 :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####***********
 ====   -:                *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####**********
 :+=+.   =               .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######*********
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

const int MAX_N = 200001;

ll count_swaps(vector<int> owo)
{
    ll n = owo.size();
    map<ll,vll> memo;
    vll arr;
    ll num;
    for(int i=0;i<n;i++)
    {
      num=owo[i];
      arr.push_back(num);
      if(memo.find(num)==memo.end())
      {
        memo[num]=vll({i});
      }
      else
      {
        memo[num].push_back(i);
      }
    }
    vector<bool> solved(n,false);
    vll cnt(n+1,0);
    ll curr=2;
    for(int i=0;i<n;i++)
    {
      num=arr[i];
      if(solved[i])
        continue;
      int j=memo[-num][cnt[abs(num)]];
      solved[i]=solved[j]=true;
      if(num<0)
      {
        arr[i]=curr-1;
        arr[j]=curr;
      }
      else
      {
        arr[i]=curr;
        arr[j]=curr-1;
      }
      cnt[abs(num)]+=1;
      curr+=2;
    }
    /*
    for(auto num:arr)
      cout << num << " ";
    cout << endl;
    */
    ll ans = 0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            ans += arr[i] > arr[j];
    return ans;
}
/*
int main()
{
    cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
}
*/

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