# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
147346 | joylintp | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>#include "shoes.h" using namespace std; bool visit[200011] = {};long long n, ret = 0, bit[200011] = {}, s[200011], ans[200011];queue<int> Left[100006], Right[100006]; void bld(void){ for (int i = 2; i <= n + 10; i++) bit[i] = i - max(1, i - (i & -i));} long long sum(int x){ long long ret = 0; for (int i = x; i >= 1; i -= (i & -i)) ret += bit[i]; return ret;} void edt(int x, int k){ for (int i = x; i <= n; i += (i & -i)) bit[i] -= k;} long long count_swaps(vector<int> in){ n = in.size(); s[0] = 0; for (int i = 1; i <= n; i++) { s[i] = in[i - 1]; if (s[i] < 0) Left[-s[i]].push(i); else Right[s[i]].push(i); } bld(); int cnt = 0, pos, tar; for (int i = 1; i <= n; i++) { if (visit[i]) continue; tar = -abs(s[i]); pos = Left[-tar].front(), Left[-tar].pop(); ans[cnt++] = tar; visit[pos] = true; ret += sum(pos); edt(pos, 1); tar = -ans[cnt - 1]; pos = Right[tar].front(), Right[tar].pop(); ans[cnt++] = tar; visit[pos] = true; ret += sum(pos); edt(pos, 1); } return ret;}