Submission #1235839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235839		vyaduct	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1095 ms	1114112 KiB

shoes

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

ll brute(const vector<int> &p){
  int n = p.size()/2;
  ll ans = 1e18;
  bool ok=true;
  for (int i=0;i<n;i++){
    if (p[2*i] > 0 || p[2*i+1] < 0 || (p[2*i] != -p[2*i+1])){
      ok = false;
      int cur=0;
      vector<int> q = p;
      int idx = (p[2*i]>0?2*i:2*i+1);
      int j;
      for (int l=0;l<n;l++) {
        if (p[2*l]<0 && p[2*l+1]>0 && -p[2*l] == p[2*l+1]){
          continue;
        }
        if (p[2*l] == -p[idx]) {
          j = 2*l;
          break;
        }
        if (p[2*l+1] == -p[idx]) {
          j = 2*l+1;
          break;
        }
      }
      if (j <= idx){
        for (int l=j;l+1<=idx;l++){
          swap(q[l], q[l+1]);
          cur++;
        }
      } else {
        for (int l=j;l-1>=idx;l--){
          swap(q[l], q[l-1]);
          cur++;
        }
      }
      ans = min(ans, brute(q)+cur);
    }
  }
  return ok?0:ans;
}

ll count_swaps(vector<int> s) {
  return brute(s);
}

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