이 제출은 이전 버전의 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 = 1e5 + 4 ;
ll BIT[MAXN];
bool vis[MAXN];
vector<ll> adj[MAXN];
ll n ;
void update ( ll idx , ll x)
{
while(idx<=MAXN)
{
BIT[idx]+=x;
idx+=idx&(-idx);
}
}
ll getsum(ll idx)
{
ll sum =0;
while(idx>0)
{
sum+=BIT[idx];
idx-=idx&(-idx);
}
return sum;
}
ll getran(ll a , ll b)
{
if(a)
return getsum(b)-getsum(a-1);
return getsum(b);
}
ll get_id(ll x){
if(x > 0)return x;
else return -x+n;
}
long long count_swaps (vector<int>s)
{
n = s.size()/2;
set<pair<ll,ll>>pq ;
ll ans = 0 ;
for(ll i =0 ;i <s.size();i++)
{
pq.insert({i,s[i]});
if(s[i]>0)adj[s[i]].pb(i);
else
{
adj[get_id(s[i])].pb(i);
}
}
for(auto it : adj)
{
reverse(all(it));
}
while(pq.size())
{
if(vis[pq.begin()->first])
{
pq.erase(pq.begin());
continue;
}
ll cur = -pq.begin()->second;
ll idx = get_id(cur);
ll to = adj[idx].back();
adj[get_id(-cur)].pop_back();
ll dist=(to+getran(to,MAXN-1))-(pq.begin()->first+getran(pq.begin()->first,MAXN-1));
if(pq.begin()->second < 0)dist--;
ans +=dist;
vis[pq.begin()->first]=1;
vis[to]=1;
update(to,1);
}
return ans ;
}
/*
int 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;
}
*/
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll 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... |