Submission #144182

#	Time	Username	Problem	Language	Result	Execution time	Memory
144182		xiaowuc1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	943 ms	146904 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int BIT_SZ = 200005;
int bit[BIT_SZ];
void inc(int idx) {
  idx += 2;
  while(idx < BIT_SZ) {
    bit[idx]++;
    idx += idx & -idx;
  }
}
int qry(int idx) {
  idx += 2;
  int ret = 0;
  while(idx) {
    ret += bit[idx];
    idx -= idx & -idx;
  }
  return ret;
}

ll count_swaps(vector<int> v) {
  ll ret = 0;
  map<int, queue<int>> dp;
  for(int i = 0; i < v.size(); i++) {
    dp[v[i]].push(i);
  }
  for(int i = 0; i < v.size(); i++) {
    if(!dp.count(v[i])) continue;
    if(dp[v[i]].front() != i) {
      assert(dp[v[i]].front() > i);
      continue;
    }
    if(v[i] > 0) ret++;
    dp[v[i]].pop();
    if(dp[v[i]].size() == 0) dp.erase(v[i]);
    inc(i);
    assert(dp[-v[i]].size());
    int other = dp[-v[i]].front(); dp[-v[i]].pop();
    if(dp[-v[i]].size() == 0) dp.erase(-v[i]);
    ret += other - qry(other);
    inc(other);
  }
  return ret;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
shoes.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); 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