이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#pragma GCC optimize ("Ofast","unroll-loops")
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
const ll MAXN = 6e5 + 4 ;
vector<int> pos[MAXN];
bool used[MAXN];
ll bit[MAXN];
ll n;
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(vector<int> s) {
long long ans = 0;
n = s.size()/2;
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 <= 2*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+segm(to_pos,MAXN-1))-(qwe.begin()->first+segm(qwe.begin()->first,MAXN-1));
if(qwe.begin()->second < 0)dist--;
ans+=dist;
used[qwe.begin()->first] = 1;
used[to_pos] = 1;
upd(to_pos,1);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45: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... |