Submission #990816

#	Time	Username	Problem	Language	Result	Execution time	Memory
990816		ChottuF	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	70 ms	20952 KiB

shoes

  #include "shoes.h"
  #include <bits/stdc++.h>
  using namespace std;

  vector<int> tree;

  int nc;

  int query(int a, int b){
      a += nc;
      b += nc;
      int s = 0;
      while (a <= b){
          if (a%2){
              s += tree[a++];
          }
          if (b%2 == 0){
              s += tree[b--];
          }
          a /= 2;
          b /= 2;
      }
      return s;
  }

  void update(int k, int x){
      k += nc;
      tree[k] = x;
      k /= 2;
      while (k >= 1){
          tree[k] = tree[2*k] + tree[2*k+1];
          k /= 2;
      }
  }

  long long count_swaps(vector<int> s) {
      int n = s.size();
      vector<vector<int>> pos(n), neg(n);
      for (int i = 0; i<n; i++){
          int g = abs(s[i]);
          if (s[i] < 0){
              neg[g].push_back(i);
          }
          else{
              pos[g].push_back(i);
          }
      }
      for (int i = 0; i<n; i++){
          reverse(pos[i].begin(),pos[i].end());
          reverse(neg[i].begin(),neg[i].end());
      }
      nc = 1;
      while ((1<<nc) < n) nc++;
      nc = 1<<nc;
      tree.resize(2*nc);
      for (int i = 0; i<n; i++){
          tree[nc+i] = 1;
      }
      for (int i = nc-1; i>=1; i--){
          tree[i] = tree[2*i] + tree[2*i+1];
      }
      long long ans = 0;
      for (int i = 0; i<n; i++){
          int val = s[i];
          int g = abs(s[i]);
          if (s[i] > 0){
              if (pos[g].empty() || pos[g].back() != i) continue;
              pos[g].pop_back();
          }
          else{
              if (neg[g].empty() || neg[g].back() != i) continue;
              neg[g].pop_back();
          }
          int ind = -1;
          int rev = -s[i];
          if (rev > 0){
              ind = pos[g].back();
              pos[g].pop_back();
          }
          else{
              ind = neg[g].back();
              neg[g].pop_back();
          }
          ans += query(i+1,ind-1);
          if (s[i] > 0) ans++;
          update(i,0);
          update(ind,0);
      }
      return ans;
  }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:64:15: warning: unused variable 'val' [-Wunused-variable]
   64 |           int val = s[i];
      |               ^~~

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