This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 1005;
int bestLeft[MAXN], bestRight[MAXN];
int moveElement(int i, int j, vector <int> &s)
{
int cnt = 0;
while(j>i)
{
cnt++;
swap(s[j-1], s[j]);
j--;
}
return cnt;
}
int calcValue(int num, int index)
{
int sum = (bestLeft[num] - index) + (bestRight[num] - (index+1));
if(bestLeft[num]>bestRight[num]) sum++;
return sum;
}
long long count_swaps(vector <int> s)
{
int answer = 0;
for(int index = 0;index<s.size();index+=2)
{
memset(bestLeft, -1, sizeof(bestLeft));
for(int i = s.size()-1;i>=index;i--)
{
if(s[i]<0) bestLeft[ -s[i] ] = i;
else bestRight[ s[i] ] = i;
}
int bestIndex = -1;
/*
for(int i = 1;i<=s.size()/2;i++)
{
if(bestLeft[i]==-1) continue;
if(bestIndex==-1) bestIndex = i;
else if(calcValue(bestIndex, index)>calcValue(i, index))
{
bestIndex = i;
}
}
if(bestLeft[bestIndex]>bestRight[bestIndex]) bestRight[bestIndex]++;
*/
bestIndex = abs(s[index]);
//cout << " " << bestIndex << '\n';
answer += moveElement(index, bestLeft[bestIndex], s);
answer += moveElement(index+1, bestRight[bestIndex], s);
}
//for(int i = 0;i<s.size();i++) cout << s[i] << " ";
//cout << '\n';
return answer;
}
Compilation message (stderr)
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:36:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int index = 0;index<s.size();index+=2)
~~~~~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |