Submission #297336

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
2973362020-09-11 13:54:06SaboonArranging Shoes (IOI19_shoes)C++17
45 / 100
379 ms27920 KiB
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
map<int,set<int>> S;
long long count_swaps(vector<int> a){
vector<pair<int,int>> Joft;
for (int i = 0; i < a.size(); i++){
int x = a[i];
if (!S[-x].empty()){
Joft.push_back({*S[-x].begin(),i});
S[-x].erase(S[-x].begin());
}
else
S[x].insert(i);
}
sort(Joft.begin(), Joft.end(), [](pair<int,int> A, pair<int,int> B){
return A.first+A.second < B.first+B.second;
});
long long ret = 0;
int now = 0;
for (int i = 0; i < a.size(); i+=2){
int v = Joft[now].first, u = Joft[now].second;
now ++;
if (a[v] > a[u])
ret += 2;
ret += abs(i-v);
ret += abs(i+1-u);
}
return ret/2;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
shoes.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 0; i < a.size(); i+=2){
      |                  ~~^~~~~~~~~~
#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...