Submission #899421

#	Time	Username	Problem	Language	Result	Execution time	Memory
899421		rxlfd314	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	62 ms	16024 KiB

shoes

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

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

struct BIT {
  vt<int> fen;
  BIT(int n) {
    fen.resize(n);
  }
  void upd(int i, int v) {
    for (; i < size(fen); i += i+1 & -i-1)
      fen[i] += v;
  }
  int qry(int i) {
    int ret = 0;
    for (; ~i; i -= i+1 & -i-1)
      ret += fen[i];
    return ret;
  }
  int qry(int l, int r) {
    return qry(r) - qry(l-1);
  }
};

ll count_swaps(vt<int> s) {
  const int N = size(s) >> 1;
  vt<int> A[N], B[N];
  FOR(i, 0, 2*N-1)
    (s[i] > 0 ? B[s[i]-1] : A[-s[i]-1]).push_back(i);
  
  int L[N], R[N], ii = 0;
  ll ans = 0;
  FOR(i, 0, N-1)
    FOR(j, 0, size(A[i])-1) {
      L[ii] = A[i][j], R[ii] = B[i][j];
      if (L[ii] > R[ii])
        ans++, swap(L[ii], R[ii]);
      ii++;
    }
  
  int ord[N];
  iota(ord, ord+N, 0);
  sort(ord, ord+N, [&](const int &a, const int &b) {
    return L[a] < L[b];
  });
  
  BIT fen(2*N);
  FOR(x, 0, N-1) {
    int i = ord[x];
    ans += R[i] - L[i] - 1 - (L[i] + 1 < R[i]) * fen.qry(L[i]+1, R[i]-1);
    fen.upd(R[i], 1);
  }
  
  return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void BIT::upd(int, int)':
shoes.cpp:20:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   20 |     for (; i < size(fen); i += i+1 & -i-1)
      |                                ~^~
shoes.cpp: In member function 'int BIT::qry(int)':
shoes.cpp:25:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   25 |     for (; ~i; i -= i+1 & -i-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