Submission #249219

#TimeUsernameProblemLanguageResultExecution timeMemory
249219Dilshod_ImomovArranging Shoes (IOI19_shoes)C++17
45 / 100
165 ms139000 KiB
# include <bits/stdc++.h> # define ll long long # define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX_N = 100007; ll count_swaps( vector < int > s ) { speed; ll n = s.size(), sz = 0; ll ans = 0; vector < int > ids, used(n); vector < queue < int > > vc(2 * MAX_N); for ( int i = 0; i < n; i++ ) { s[i] += MAX_N; vc[s[i]].push( i ); } // cout << "Done 1" << endl; for ( int i = 0; i < n; i++ ) { if ( used[i] ) { continue; } s[i] -= MAX_N; int l = i, r = vc[-s[i] + MAX_N].front(); // cout << "Done 2 " << l << ' ' << r << endl; vc[ s[i] + MAX_N ].pop(); int rr = r; used[r] = 1; vc[-s[i] + MAX_N].pop(); int x = lower_bound( ids.begin(), ids.end(), i ) - ids.begin(); x = sz - x; l += x; x = lower_bound( ids.begin(), ids.end(), r ) - ids.begin(); x = sz - x; r += x; ans += r - l - 1; if ( s[i] > 0 ) { ans++; } sz++; ids.push_back( rr ); } return ans; } /* int main() { ll n; cin >> n; vector < int > S(2 * n); for ( ll i = 0; i < 2 * n; i++ ) { cin >> S[i]; } cout << count_swaps( S ); } */
#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...