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 <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
const int MAXN = 2005 ;
vector<int> posR[MAXN],posL[MAXN] ;
long long count_swaps(std::vector<int> s) {
ll ans = 0;
int n = sz(s)/2 ;
for(int i=0;i<sz(s);i++ ){
int a = s[i] ;
if( a > 0 )posR[a].pb(i);
else posL[-a].pb(i) ;
}
for(int i = 1 ; i <= n ; i++ ){
reverse(all(posR[i]));
reverse(all(posL[i]));
}
for(int i = 0 ; i < n ; i++ ){
int l = i * 2 , r = i*2 + 1 ;
int bestL , bestR , toadd = 1e9 , bestS = -1;
for(int j = 1 ; j <= n ; j++ ){
while ( !posL[j].empty() && l > posL[j].back() )posL[j].pop_back();
if( posL[j].empty() )continue ;
int currL = posL[j].back();
while ( !posR[j].empty() ){
if( posR[j].back() < currL && posR[j].back() < l )posR[j].pop_back();
else break ;
}
int currR = posR[j].back();
if( currR < currL )
currR ++ ;
// cout << currL << " " << currR << " " << currL + currR - l - r << endl;
if( currL + currR - l - r <= toadd)
bestR = currR , bestL = currL , toadd = currL + currR - l - r ,bestS = j;
}
posR[bestS].pop_back();
posL[bestS].pop_back();
for(int j = 1 ; j <= n ; j++ ){
for(int& x : posL[j]){
if( bestL > x )x++;
if( bestR > x )x++ ;
}
sort(all(posL[j]));
reverse(all(posL[j]));
for(int& x : posR[j]){
if( bestL > x )x++;
if( bestR > x )x++ ;
}
sort(all(posR[j]));
reverse(all(posR[j]));
}
// cout << "for i = "<<i << endl;
// cout << bestL << " " << bestR << " " <<toadd<< endl;
ans += 1LL*toadd ;
}
return ans;
}
// int main() {
// int n;
// assert(1 == scanf("%d", &n));
// vector<int> S(2 * n);
// for (int i = 0; i < 2 * n; i++)
// assert(1 == scanf("%d", &S[i]));
// fclose(stdin);
// long long result = count_swaps(S);
// printf("%lld\n", result);
// fclose(stdout);
// return 0;
// }
Compilation message (stderr)
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:47:5: warning: 'bestR' may be used uninitialized in this function [-Wmaybe-uninitialized]
if( bestR > x )x++ ;
^~
shoes.cpp:46:5: warning: 'bestL' may be used uninitialized in this function [-Wmaybe-uninitialized]
if( bestL > x )x++;
^~
# | 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... |