Submission #744083

#	Time	Username	Problem	Language	Result	Execution time	Memory
744083		veehz	Permutation (APIO22_perm)	C++17	100 / 100	13 ms	340 KiB

perm

#include "perm.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void normalize(vector<float>& a) {
  vector<float> b = a;
  sort(b.begin(), b.end());
  map<float, int> mp;
  for (int i = 0; i < (int)b.size(); i++) mp[b[i]] = i;
  for (int i = 0; i < (int)a.size(); i++) a[i] = mp[a[i]];
}

void insert(vector<float>& a, int x) {
  int n = a.size();
  if (x == 0) {
    a.push_back(n);
    a.push_back(n + 1);
    return;
  } else if (x == 1) {
    a.push_back(n);
    a.push_back(n + 1);
    a.push_back(-1);
    normalize(a);
    return;
  } else if (x == 2) {
    a.push_back(n);
    a.push_back(-1);
    a.push_back(n + 1);
    normalize(a);
    return;
  } else {
    // x = 3
    bool oneThenZero = false;
    for (auto& i : a) {
      if (i == 1) {
        oneThenZero = true;
        break;
      } else if (i == 0) {
        break;
      }
    }
    if (oneThenZero) {
      a.push_back(n);
      a.push_back(n + 1);
      a.push_back(1.5);
      normalize(a);
      return;
    } else {
      a.push_back(n);
      a.push_back(-1);
      a.push_back(n + 1);
      a.push_back(-2);
      normalize(a);
      return;
    }
  }
}

vector<int> construct_permutation(ll k) {
  vector<int> a;
  while (k) {
    a.push_back(k % 4);
    k /= 4;
  }
  reverse(a.begin(), a.end());
  vector<float> ans;
  switch (a[0]) {
    case 1:
      break;
    case 2:
      ans.push_back(0);
      break;
    case 3:
      ans.push_back(1);
      ans.push_back(0);
      break;
  }
  for (int i = 1; i < (int)a.size(); i++) {
    insert(ans, a[i]);
  }
  vector<int> res(ans.begin(), ans.end());
  return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90