Submission #399049

#TimeUsernameProblemLanguageResultExecution timeMemory
399049mshandilyaArranging Shoes (IOI19_shoes)C++14
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; long long count_swaps(std::vector<int> s) { long long N = s.size(), left_pair = 0, right_pair = 0, sort_inversions = 0, total_inversions = 0; std::vector<int> position(N); std::vector<queue<int>> compensated_inversions(N+1); for(int i = 2*N-1; i>=0; i--) { if(s[i]<0) { compensated_inversions[abs(s[i])].push(left_pair); left_pair++; position[s[i]] = N-left_pair; } else if(!compensated_inversions[s[i]].empty()) { total_inversions += left_pair - compensated_inversions[s[i]].front(); compensated_inversions[s[i]].pop(); } } for(int i = 0; i<2*N-1; i++) { if(s[i]>0) { int cpos = position[s[i]]; for(int j = i+1; j<2*N-1; j++) if(s[j]>0 && position[s[j]]<cpos) sort_inversions++; } } return (total_inversions+sort_inversions); }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:7:41: warning: unused variable 'right_pair' [-Wunused-variable]
    7 |  long long N = s.size(), left_pair = 0, right_pair = 0, sort_inversions = 0, total_inversions = 0;
      |                                         ^~~~~~~~~~
#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...