이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 110;
bool used[N];
int fenwick[N];
void update(int ind, int diff, int n) {
while (ind <= n) {
fenwick[ind] += diff;
ind += (ind & (-ind));
}
}
int sm(int ind) {
int ans = 0;
while (ind > 0) {
ans += fenwick[ind];
ind -= (ind & (-ind));
}
return ans;
}
ll count_swaps(vector<int> S) {
int n = (int)S.size() / 2;
if (n <= 1000) {
ll ans = 0;
for (int i = 0; i < n; i++) {
int ind1 = -1, ind2 = -1;
for (int j = 2 * i; j < 2 * n; j++) {
if (S[j] < 0) {
ind1 = j;
break;
}
}
int x = S[ind1];
for (int j = ind1; j > 2 * i; j--) {
ans++;
swap(S[j], S[j - 1]);
}
for (int j = 2 * i + 1; j < 2 * n; j++) {
if (S[j] == -x) {
ind2 = j;
break;
}
}
for (int j = ind2; j > 2 * i + 1; j--) {
ans++;
swap(S[j], S[j - 1]);
}
}
return ans;
}
bool ch = true;
for (auto& it : S) {
if (abs(it) != abs(S[0])) ch = false;
}
if (ch) {
//cout << "?\n";
vector <int> a;
vector <int> b;
for (int i = 0; i < 2 * n; i++) {
if (S[i] < 0) a.push_back(i + 1);
else b.push_back(i + 1);
update(i + 1, 1, 2 * n);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += sm(a[i] - 1); update(a[i], -1, 2 * n);
ans += sm(b[i] - 1); update(b[i], -1, 2 * n);
}
return ans;
}
}
/*
int main() {
cout << count_swaps({ -2, 2, 2, -2, -2, 2 }) << "\n";
}
*/
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
78 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |