Submission #739780

#TimeUsernameProblemLanguageResultExecution timeMemory
739780nicolaevArranging Shoes (IOI19_shoes)C++14
10 / 100
1080 ms21808 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define ll int #define all(v) v.begin(), v.end() #define fr(n) for(ll i=0;i<n;++i) #define ctz(x) __builtin_ctzll(x) #define clz(x) __builtin_clzll(x) #define pcount(x) __builtin_popcountll(x) const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; // #define cin fin // #define cout fout // ifstream fin // ofstream fout //const ll maxn = 3e5 + 5; //int f[maxn],nf[maxn],inv[maxn]; //const int M=998244353; //void init(){ //inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M; //f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M; //} //int C(int x,int y){return 1ll*f[x]*nf[y]%M*nf[x-y]%M;} long long count_swaps(vector<ll> s){ ll n=s.size(); vector< set<ll> > v(n+4); for(ll i=0; i<n; i++){ if(s[i]<0){ v[abs(s[i])+n/2].insert(i); } else v[s[i]].insert(i); } long long ans=0; set<ll> st; for(ll i=0; i<s.size(); i++){ if(s[i]<0){ if(v[abs(s[i])+n/2].empty()) continue; v[abs(s[i])+n/2].erase(i); set<ll> ::iterator it=v[abs(s[i])].begin(); ans+=*it-i-1; for(auto itr=st.begin(); itr!=st.end(); itr++){ if(*itr>i && *itr<*it){ ans--; } } // ll temp=*it; // s.erase(s.begin() + temp); st.insert(*it); v[abs(s[i])].erase(it); } else{ if(v[s[i]].empty()) continue; v[s[i]].erase(i); set<ll> ::iterator it=v[n/2+s[i]].begin(); ans+=*it-i; for(auto itr=st.begin(); itr!=st.end(); itr++){ if(*itr>i && *itr<*it){ ans--; } } // s.erase(s.begin()+ (*it)); st.insert(*it); v[n/2+s[i]].erase(it); } // cout<<ans; } return ans; } // int main(){ // vector<ll> s; // ll n;cin>>n; // fr(n){ // ll x;cin>>x;s.push_back(x); // } // cout<<count_swaps(s); // }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(ll 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...