제출 #295703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295703		tzero	Arranging Shoes (IOI19_shoes)	C++14	70 / 100	1095 ms	29048 KiB

shoes

#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <cassert>
#include <cstring>
using namespace std;
using ll = long long;
const int maxn = (int)1e5 + 7;
int t[8 * maxn], lz[8 * maxn];
int n;

void update(int v, int tl, int tr, int l, int r) {
  if(tl > r || tr < l) {
    return;
  } else if(tl >= l && tr <= r) {
    lz[v]++;
  } else {
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r);
    update(2 * v + 1, tm + 1, tr, l, r); 
  }
}

int query(int v, int tl, int tr, int i) {
  if(tl > i || tr < i) {
    return -1;
  }
  if(lz[v] > 0) {
    t[v] += lz[v];
    if(tl != tr) {
      lz[2 * v] += lz[v];
      lz[2 * v + 1] += lz[v];
    }
    lz[v] = 0;
  }
  if(tl == tr) {
    return t[v];
  } else {
    int tm = (tl + tr) / 2;
    int ans = query(2 * v, tl, tm, i); 
    if(ans != -1) return ans;
    ans = query(2 * v + 1, tm + 1, tr, i);
    return ans;
  }
}

ll count_swaps(vector<int> s) {
  n = (int)s.size();

  bool same_size = true;
  for(int i = 0; i < n; i++) {
    if(i > 0 && abs(s[i]) != abs(s[i - 1])) same_size = false;
  }

  if(same_size) {
    ll move_left = 0, move_right = 0;
    int found_left = 0, found_right = 0;
    for(int i = 0; i < n; i++) {
      if(s[i] < 0) {
        int pos = found_left * 2;
        move_left += abs(i - pos);
        found_left++;
      } else {
        int pos = found_right * 2 + 1;
        move_right += abs(i - pos);
        found_right++;
      }
    }
    return min(move_left, move_right);
  }

  memset(t, 0, sizeof(t));
  memset(lz, 0, sizeof(lz));

  ll ans = 0;

  int half = n / 2;
  vector<vector<int> > positions(n + 1);
  set<int> indexes_left;
  for(int i = 0; i < n; i++) {
    positions[s[i] + half].push_back(i); 
    indexes_left.insert(i);
  }

  for(int pos_right = n - 1; pos_right >= 1; pos_right -= 2) {
    int real_idx = *prev(indexes_left.end());
    int idx_left = positions[-s[real_idx] + half].back();
    int pos_left = idx_left - query(1, 0, n - 1, idx_left);

    assert(s[real_idx] == s[idx_left] == 0);

    ans += pos_right - pos_left;
    if(s[real_idx] > 0) ans--;

    update(1, 0, n - 1, idx_left, n - 1);
    positions[s[real_idx] + half].pop_back();
    positions[-s[real_idx] + half].pop_back();

    auto it = lower_bound(indexes_left.begin(), indexes_left.end(), real_idx);
    indexes_left.erase(it);
    it = lower_bound(indexes_left.begin(), indexes_left.end(), idx_left);
    indexes_left.erase(it);
  }

  return ans;
}

int _main() {
  int n;
  scanf("%d", &n);

  vector<int> _s(2 * n);
  for(int i = 0; i < 2 * n; i++) {
    scanf("%d", &_s[i]);
  }

  printf("%lld\n", count_swaps(_s));

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/9/cassert:44,
                 from shoes.cpp:5:
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:91:24: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   91 |     assert(s[real_idx] == s[idx_left] == 0);
shoes.cpp: In function 'int _main()':
shoes.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
shoes.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |     scanf("%d", &_s[i]);
      |     ~~~~~^~~~~~~~~~~~~~

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