Submission #533023

#	Time	Username	Problem	Language	Result	Execution time	Memory
533023		kebine	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	87 ms	21436 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
 
template <typename T>
struct Fenwick {
    vector<T> t;
    T n;
    Fenwick(T n) : n(n) {
        t.resize(n);
    }
    T g(T r){
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += t[r];
        return ret;
    }
    T sum(T l, T r){
        return g(r) - g(l - 1);
    }
    void add(T i, T v){
        for(;i < n; i = i | (i + 1))
            t[i] += v;
    }
};
 
 
long long count_swaps(vector<int> s){
  long long n = s.size(), ans = 0;
  const int N = 1e5 + 1;
  vector<int> L[n + 1], R[n + 1];
  for(int i=0;i<n;i++)
  {
    if(s[i] < 0) L[-s[i]].push_back(i);
    else R[s[i]].push_back(i);
  }
  Fenwick<long long> fw(n + 1);
  vector<pair<int,int>> v;
  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<L[i].size();j++)
    {
      if(L[i][j] > R[i][j])
      {
        ans++;
        swap(L[i][j], R[i][j]);
      }
      v.push_back({L[i][j], R[i][j]});
    }
  }
  sort(v.begin(), v.end());
  for(auto i : v)
  {
    // cout << i.first << " " << i.second << " " << '\n';
    ans += (i.second - i.first - 1) - fw.sum(i.first + 1, i.second - 1);
    fw.add(i.second, 1);
    fw.add(i.first, 1);
  }
  return ans;
}
 
 
// signed main(){
//   int n;
//   cin >> n;
//   vector<int> t(2*n);
//   for(int i=0;i<2*n;i++) cin >> t[i];
//   cout << count_swaps(t) << '\n';
// }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int j=0;j<L[i].size();j++)
      |                 ~^~~~~~~~~~~~
shoes.cpp:29:13: warning: unused variable 'N' [-Wunused-variable]
   29 |   const int N = 1e5 + 1;
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15