제출 #443232

#제출 시각아이디문제언어결과실행 시간메모리
443232mkisicArranging Shoes (IOI19_shoes)C++14
45 / 100
75 ms12784 KiB
#include "shoes.h" #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define TRACE(x) cerr << #x << ' ' << x << endl #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define _ << " " << #define pb push_back const int MAXN = 200100; struct Fenwick { int p[MAXN]; void clear() { memset(p, 0, sizeof p); } void add(int x) { for (int i = x; i > 0; i -= i &- i) p[i]++; } int get(int x) { int ret = 0; for (int i = x; i < MAXN; i += i &- i) ret += p[i]; return ret; } }loga; long long solve(vector <int> p, int start, int T) { vector <int> pos; vector <int> v[MAXN]; int n = p.size(); pos.resize(n); int t = start; REP(i, n) { if (p[i]/abs(p[i]) == T) { v[max(p[i], -p[i])].pb(t); pos[i] = t; t += 2; } } REP(i, MAXN) reverse(v[i].begin(), v[i].end()); REP(i, n) { if (p[i]/abs(p[i]) != T) { int x = v[max(p[i], -p[i])].back(); v[max(p[i], -p[i])].pop_back(); if (p[i] < 0) x--; else x++; pos[i] = x; } } long long inv = 0; loga.clear(); REP(i, n) { inv += loga.get(pos[i] + 1); loga.add(pos[i] + 1); } return inv; } long long count_swaps(std::vector<int> s) { return min(solve(s, 0, -1), solve(s, 1, 1)); }
#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...