이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <math.h>
#include <cassert>
#include <cstring>
using namespace std;
using ll = long long;
const int maxn = (int)1e5 + 7;
int t[8 * maxn], lz[8 * maxn];
int n;
void tle() {
assert(false);
while(true) {
n--;
n++;
}
}
void update(int v, int tl, int tr, int l, int r) {
if(tl > r || tr < l) {
return;
} else if(tl >= l && tr <= r) {
lz[v]++;
} else {
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r);
update(2 * v + 1, tm + 1, tr, l, r);
}
}
int query(int v, int tl, int tr, int i) {
if(tl > i || tr < i) {
return -1;
}
if(lz[v] > 0) {
t[v] += lz[v];
if(tl != tr) {
lz[2 * v] += lz[v];
lz[2 * v + 1] += lz[v];
}
lz[v] = 0;
}
if(tl == tr) {
return t[v];
} else {
int tm = (tl + tr) / 2;
int ans = query(2 * v, tl, tm, i);
if(ans != -1) return ans;
ans = query(2 * v + 1, tm + 1, tr, i);
return ans;
}
}
ll count_swaps(vector<int> s) {
n = (int)s.size();
bool same_size = true;
for(int i = 0; i < n; i++) {
if(i > 0 && abs(s[i]) != abs(s[i - 1])) same_size = false;
}
if(n == 2) {
if(s[0] < 0) return 0;
else return 1;
} else if(same_size) {
ll move_left = 0, move_right = 0;
int found_left = 0, found_right = 0;
for(int i = 0; i < n; i++) {
if(s[i] < 0) {
int pos = found_left * 2;
move_left += abs(i - pos);
found_left++;
} else {
int pos = found_right * 2 + 1;
move_right += abs(i - pos);
found_right++;
}
}
return min(move_left, move_right);
} else {
memset(t, 0, sizeof(t));
memset(lz, 0, sizeof(lz));
vector<vector<int> > positions(n + 1);
for(int i = 0; i < n; i++) {
positions[s[i] + (n / 2)].push_back(i);
}
int ans = 0;
for(int position = n - 1; position >= 1; position -= 2) {
int right_idx = position + query(1, 0, n - 1, position);
if(-s[right_idx] + (n / 2) < 0) tle();
int xx = -s[right_idx] + (n / 2);
if(positions[xx].size() == 0) tle();
int left_idx = positions[xx].back();
int closest = left_idx - query(1, 0, n - 1, left_idx);
ans += position - closest;
if(s[right_idx] > 0) ans--;
positions[s[right_idx] + (n / 2)].pop_back();
positions[-s[right_idx] + (n / 2)].pop_back();
update(1, 0, n - 1, left_idx, position);
}
return ans;
}
}
int _main() {
int n;
scanf("%d", &n);
vector<int> _s(2 * n);
for(int i = 0; i < n; i++) {
scanf("%d", &_s[i]);
}
printf("%lld\n", count_swaps(_s));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'int _main()':
shoes.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
116 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
shoes.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | scanf("%d", &_s[i]);
| ~~~~~^~~~~~~~~~~~~~
# | 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... |