제출 #1022647

#제출 시각아이디문제언어결과실행 시간메모리
1022647CodeAssignmentArranging Shoes (IOI19_shoes)C++17
10 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define trav(a, x) for (auto &a : x) #define pb push_back #define el "\n"; //#define dbg(x) cerr << "\e[92m" << #x << " = " << x << "\e[97m" << el; #define dbg(x) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; ll count_swaps(vector<int> S) { assert(sz(S) % 2 == 0); ll n = sz(S) / 2; // number of pairs vi a = S; vector<vll> pos(2 * n + 1); rep(i, 0, 2*n) { dbg(i); pos[a[i] + n].pb(i); dbg(a[i]); } ll ans = 0; ll ind = 0; while(ind < 2 * n) { ll cur = a[ind]; auto nxt = upper_bound(all(pos[-cur + n]), ind); assert(nxt != pos[-cur + n].end()); assert(a[*nxt] == -cur); vi temp; rep(i, 0, ind) { temp.pb(a[i]); } temp.pb((cur < 0 ? cur : -cur)); temp.pb((cur < 0 ? -cur : cur)); rep(i, ind + 2, 2*n) { temp.pb(a[i]); } ans += (*nxt) - ind - (cur < 0 ? 1 : 0); //assert(sz(temp) == 2 * n); ind += 2; swap(a, temp); pos.assign(2 * n + 1, vll()); rep(i, 0, 2*n) { pos[a[i] + n].pb(i); } } return ans; }
#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...