Submission #199103

#TimeUsernameProblemLanguageResultExecution timeMemory
199103redaArranging Shoes (IOI19_shoes)C++14
100 / 100
205 ms33528 KiB
#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; }

Compilation message (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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...