제출 #242416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242416		quocnguyen1012	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	205 ms	140664 KiB

shoes

#ifndef LOCAL
#include "shoes.h"
#endif // LOCAL
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int N;
queue<int> same[2 * maxn];
int bit[2 * maxn], go[2 * maxn];
int rem[2 * maxn];

void upd(int i, int v)
{
  for(++i; i < 2 * maxn; i += i & -i)
    bit[i] += v;
}

int sum(int i)
{
  int res = 0;
  for(++i; i; i -= i & -i)
    res += bit[i];
  return res;
}

long long count_swaps(vector<int> a)
{
  ll res = 0;
  N = a.size();
  for(int i = 0; i < N; ++i){
    if(same[abs(a[i])].empty() || a[same[abs(a[i])].front()] == a[i]){
      same[abs(a[i])].push(i);
      if(a[i] > 0) ++res;
    }
    else{
      go[i] = same[abs(a[i])].front();
      go[same[abs(a[i])].front()] = i;
      same[abs(a[i])].pop();
    }
  }
  for(int i = 0; i < N; ++i)
    upd(i, 1), rem[i] = 1;
  for(int i = 0; i < N; ++i){
    assert(same[i].empty());
  }
  for(int i = 0; i < N; ++i){
    if(rem[i]){
      int nxt = go[i];
      res += sum(nxt - 1) - 1;
      rem[i] = rem[nxt] = 0;
      upd(i, -1); upd(nxt, -1);
    }
  }
  return res;
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int n; cin >> n;
  vector<int> a(2 * n);
  for(auto & it : a) cin >> it;
  cout << count_swaps(a);
}
#endif // LOCAL

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