Submission #1110810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110810		epicci23	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	277 ms	151992 KiB

shoes

#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)x.size()
 
struct Fenwick{
  vector<int64_t> fw;
  int N;
  Fenwick(int64_t _n){
  	N = _n + 15;
  	fw.assign(N,0);
  }
  void upd(int64_t c){
    for(;c<N;c+=c&-c) fw[c]++;
  }
  int64_t query(int64_t c,int64_t res=0){
  	for(;c;c-=c&-c) res+=fw[c];
  	return res;
  }
};



int64_t count_swaps(vector<int> S){
  int64_t n,ans=0; 
  n = sz(S) / 2;
  int64_t ar[2*n+5];
  for(int i=1;i<=2*n;i++) ar[i] = S[i-1];
  
  queue<int64_t> q1[n+5],q2[n+5];
 
  for(int i=1;i<=2*n;i++){
    if(ar[i]<0) q1[-ar[i]].push(i);
    else q2[ar[i]].push(i);
  }

  set<int64_t> s;
  for(int i=1;i<=2*n;i++) s.insert(i);
  Fenwick F(2*n);

  for(int i=1;i<=2*n;){
    int64_t l = *s.begin(), r;
    if(ar[l]<0){
      r = q2[-ar[l]].front();
      q2[-ar[l]].pop();
      q1[-ar[l]].pop();
    }
    else{
      r = q1[ar[l]].front();
      q2[ar[l]].pop();
      q1[ar[l]].pop();
      swap(l,r);
    }
    s.erase(l),s.erase(r);
    
    F.upd(l);
    l+=F.query(2*n)-F.query(l);
    ans+=l-i;
    i++;

    F.upd(r);
    r+=F.query(2*n)-F.query(r);
    ans+=r-i;
    i++;
  }
 
  return ans;
}

/*void _(){
  int64_t n,ans=0; cin >> n;
  int64_t ar[2*n+5];
  for(int i=1;i<=2*n;i++) cin >> ar[i];
  
  queue<int64_t> q1[n+5],q2[n+5];
 
  for(int i=1;i<=2*n;i++){
    if(ar[i]<0) q1[-ar[i]].push(i);
    else q2[ar[i]].push(i);
  }

  set<int64_t> s;
  for(int i=1;i<=2*n;i++) s.insert(i);
  Fenwick F(2*n);

  for(int i=1;i<=2*n;){
    int64_t l = *s.begin(), r;
    if(ar[l]<0){
      r = q2[-ar[l]].front();
      q2[-ar[l]].pop();
      q1[-ar[l]].pop();
    }
    else{
      r = q1[ar[l]].front();
      q2[ar[l]].pop();
      q1[ar[l]].pop();
      swap(l,r);
    }
    s.erase(l),s.erase(r);
    
    F.upd(l);
    l+=F.query(2*n)-F.query(l);
    ans+=l-i;
    i++;

    F.upd(r);
    r+=F.query(2*n)-F.query(r);
    ans+=r-i;
    i++;
  }
 
  cout << ans << '\n';
}
 
int32_t main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
}*/

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