제출 #1218292

#제출 시각아이디문제언어결과실행 시간메모리
1218292Joon_YorigamiArranging Shoes (IOI19_shoes)C++17
100 / 100
248 ms29620 KiB
/* .:-=++***#***+=:. .:-==+**##**%########***#####*=:. .-+#%%#*****############**#******#####+=: .-*%#####********###########*********#######*+-: :+#######**********########*****+********##########+-. :+##########**###******##********************###########+: :+##########*****#*******###**********************###***####*: .=###########***###*******#***************************#****#####*: :*#################******************************************######= -###################***************+****************************#####*: .=###################******************************************#****#####+. :*###################*******************************+************#*****#####: =#############**######*****#*******************++***++++++***************#####= .*###########******####*****#************+++*+**+++***++++++++***#**********#####+ -############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####* =############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*. .+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*. .*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*. .:-: .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*. .--:++=+. .**. ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*: :++===== .**. -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=: .-=++= =*. +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+: . .#. .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+: -- -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-. -=+++-. = +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=: .++====++ = ####################**##*****###***#+****#=#**** .+*###************+ ## +***######****##########+--+#%%%%+: .---:=+======+: +. ##################%#***#*****####****#**#+-####. .+###***##*******# .#: :***########***##%%%####%#=. .:=*%% ---==++=======+= -= .%#################%****#*****######-#*##*.=%#*. +=---:::.......: =: =**#########***#%%%%%%%%%%%=. .- :-:===========+= .#. :%################%%****#*****#####= :-+***#*=. .*#########%%#**#*=%%%%%%%%%%=. .---=========+= :*. -#################%%****#*****%#+-.-*#%%%@###*= +##########%%%***:+-#%%%#####*: .:=++++====+- =*.=###%############%@%****#*****#. =###%%%@@@+ ###########%%%%#*#: -*########= ..:::::-. +*+###%####%######%%+******#****#=##= -@@@@@@@+ =*###########%%%%##+ :*#######+ =%##+%####%######%+.******#*****%%#-:+@@@@%-=* +..###########%##%%%*. -####### %##=#####%###%%#%:=******#*****%*.**##*+=: . -+**####*=: - .=###############%%*: .+##### .%###%########%%%%:.#*****##*****= .+: . :-::.:--=++- : .-*##################+: :#### :##.*###########%@# #************+ .:.-==-- . +**###+*##############*: .*## -%- ############%@@-#*###*#=##***#. :. =*++*#**++*##############*- .## =# ############@@@######*#:###*##= :..+*++++***+++++*##############=.+# +: ###########%@%%%%######.=###### .=+#+++++++***+++++****############## .+ *##########%%%%%%######::######= =+++#*+++++++*#+++++******########### +: =%#%######%%%##%@######:-+######. .:------== :*++++**+++++++*#*+++++********####### -* :%%%%#####%%%##%%%#####***######* -=--------=: -*+++++++*++++++++*#**+++*=:=******+==* .*+ +%%%%###%%####%%%#####**+#######= -........:=: -++++++++++*#**##***+******++- .-******=. -*= *%%%%##%%%%%%%#%#####**++#######. :.........- .=#%%%######%##########%#+*******. .-++++*+ -*+ .*%%%%#%%#######%#####*++++######*: ......... :=#%@@%%%%%%#################*++*****=. .-++++ :**. :###%%%#%%########%####*++++*#######=-:.. -+#%%%###########################++++****#=. .-++ -*+ .######%%%%#########%###@@@%%%%######+...:----:. :*%################################%*+++++*+###- .+ :*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+. . -+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*. =##+ +#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++ -##. =%**********#######%%###############%*#####=...=. . :-=-: .###############%#******####%#####+= +* *#************#############%%#######**+*%####-.- .-:=##############%*********##%#######=: .+. *#****************##**######%%%###*: ::*#####: -:: .-+####%%%####%*********#%##########*-: =#***********************######%*- .--:=:. =. :--: .-=*###%###*********#######*#######+- .#**************************###= .:. ::... .=. +***#%##*******#########***#######+: =##**************************: :-:--. .. .+..... + =******#%#####%##########***#####**# ####**********************+. . :#########+-=:.... -: +***********##%%#***######****##**** .#%####******************- *##########*:....... ...:. #**************##*********###*##**** :#%@%%%###************* =#*******####+....... :-. *#***************%************#%#**** .#**###%%%%%######****#. =#***********#=....:-. :*#****************##*************####* *#**#****#####%%%%##### =#*************+=: .=-::..:-*#*****************##*****************## -#***#*******######%%%%= :=*#**********: ... ##*##%##*******************#******************** .%*****#*********######%. ....:-=*- :++: =#****##%####*************###******************** :. +#*****#**********####%+ ..-*#***#+=##*******##%%###********####********************* .:-:. .%#*****#**********#%%%* :=+**##########******###********#%%%%%%##****###*********************** -- =%#******#*********@#%%-. :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####************************* =-. .=. ##*******#********#%#**###*+=-:.: -######%##%###%####%%%%%##########%####%%%%##%*************####************ ==== .= :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####*********** ==== -: *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####********** :+=+. = .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######********* */ #include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector<ll>; const int MAX_N = 200001; ll splitinv_count(vll &arr,ll l,ll r) { if(l==r) return 0; ll mid=l+(r-l)/2; vll barr; vll carr; for(int i=l;i<=mid;i++) barr.push_back(arr[i]); for(int i=mid+1;i<=r;i++) carr.push_back(arr[i]); ll ans=0; ll k=l; int j=0; for(int i=0;i<barr.size();i++) { while(j<carr.size()&&barr[i]>carr[j]) { arr[k]=carr[j]; k+=1; j+=1; } ans+=j; arr[k]=barr[i]; k+=1; } while(j<carr.size()) { arr[k]=carr[j]; k+=1; j+=1; } return ans; } ll inversion_count(vll &arr,ll l,ll r) { if(l==r) return 0; ll mid=l+(r-l)/2; ll x,y,z; x=inversion_count(arr,l,mid); y=inversion_count(arr,mid+1,r); z=splitinv_count(arr,l,r); return x+y+z; } 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; */ return inversion_count(arr,0,n-1);; } /* int main() { cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...