이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shoes.h"
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
using namespace std;
const int maxn = 210000;
vector<int> pos[210000];
bitset<maxn> used;
int n;
namespace fen{
int bit[maxn];
void upd(int id,int x){
while(id < maxn){
bit[id]+=x;
id|=id+1;
}
}
int sum(int r){
int res = 0;
while(r>=0){
res+=bit[r];
r&=r+1;
r--;
}
return res;
}
int segm(int l,int r){
int ans = sum(r);
if(l)ans-=sum(l-1);
return ans;
}
}
int get_id(int x){
if(x > 0)return x;
else return -x+n;
}
long long count_swaps(std::vector<int> s) {
int ans = 0;
n = s.size();
set<pair<int,int> > qwe;
for(int i(0); i < s.size();i++){
qwe.insert({i,s[i]});
if(s[i] > 0)pos[s[i]].push_back(i);
else{
int id = get_id(s[i]);
pos[id].push_back(i);
}
}
for(int i(1); i <= n;i++){
reverse(pos[i].begin(),pos[i].end());
}
while(qwe.size()){
if(used[qwe.begin()->first]){
qwe.erase(qwe.begin());
continue;
}
int now = -qwe.begin()->second;
int id = get_id(now);
int to_pos = pos[id].back();
pos[id].pop_back();
pos[get_id(-now)].pop_back();
int dist = (to_pos+fen::segm(to_pos,maxn-1))-(qwe.begin()->first+fen::segm(qwe.begin()->first,maxn-1));
//cout << "W " << (to_pos+fen::segm(to_pos,maxn-1)) << ' ' << (qwe.begin()->first+fen::segm(qwe.begin()->first,maxn-1)) << endl;
if(qwe.begin()->second < 0)dist--;
ans+=dist;
used[qwe.begin()->first] = 1;
used[to_pos] = 1;
fen::upd(to_pos,1);
//cout << ans << ' ' << dist << endl;
}
return ans;
}
/*
6
-2 2 2 -2 -2 2
*/
/*
main(){
ios_base::sync_with_stdio(0);
int n; cin >> n;
vector<int> v;
for(int i(0); i < n;i++){
int x; cin >> x;
v.push_back(x);
}
cout << count_swaps(v);
return 0;
}*/
/*
4
2 1 -1 -2
6
-2 2 2 -2 -2 2
*/
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < s.size();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... |