제출 #1022645

#제출 시각아이디문제언어결과실행 시간메모리
1022645CodeAssignmentArranging Shoes (IOI19_shoes)C++17
10 / 100
1 ms600 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) { //dbg(1); assert(sz(S) % 2 == 0); ll n = sz(S) / 2; // number of pairs vi a = S; //dbg(2); vector<vll> pos(2 * n + 1); //dbg(3); rep(i, 0, 2*n) { dbg(i); pos[a[i] + n].pb(i); dbg(a[i]); } //dbg(4); dbg("IN"); ll ans = 0; ll ind = 0; while(ind < 2 * n) { dbg(ind); ll cur = a[ind]; dbg(cur); auto nxt = upper_bound(all(pos[-cur + n]), ind); //dbg(1); assert(nxt != pos[-cur + n].end()); assert(a[*nxt] == -cur); //dbg(2); vi temp; rep(i, 0, ind) { temp.pb(a[i]); } //dbg(2); 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; //dbg(2); swap(a, temp); //dbg(3); pos.assign(2 * n + 1, vll()); dbg(3); rep(i, 0, 2*n) { dbg(a[i]); pos[a[i] + n].pb(i); } dbg(5); } 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...