Submission #789749

#	Time	Username	Problem	Language	Result	Execution time	Memory
789749		tvladm2009	Permutation (APIO22_perm)	C++17	100 / 100	11 ms	360 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 10000;

vector<int> norm(vector<int> v) {
  vector<int> aux = v;
  sort(aux.begin(), aux.end());
  aux.resize(unique(aux.begin(), aux.end()) - aux.begin());
  map<int, int> mp;
  int cnt = 0;
  for (auto &it : aux) {
    mp[it] = cnt++;
  }
  for (auto &it : v) {
    it = mp[it];
  }
  return v;
}

vector<int> construct_permutation(ll n) {
  if (n == 1) {
    return norm({});
  } else if (n == 2) {
    return norm({0});
  } else if (n == 3) {
    return norm({1, 0});
  }
  vector<int> sol = construct_permutation(n / 4);
  if (n % 4 == 0) {
    sol.push_back(INF);
    sol.push_back(INF + 1);
  }
  if (n % 4 == 1) {
    sol.push_back(INF);
    sol.push_back(INF + 1);
    sol.push_back(-1);
  }
  if (n % 4 == 2) {
    sol.push_back(INF);
    sol.push_back(-1);
    sol.push_back(INF + 1);
  }
  if (n % 4 == 3) {
    bool one = 0, onezero = 0;
    for (auto &it : sol) {
      one |= (it == 1);
      if (it == 0) {
        onezero |= one;
      }
    }
    if (onezero == true) {
      for (auto &it : sol) {
        it *= 2;
      }
      sol.push_back(INF);
      sol.push_back(INF + 1);
      sol.push_back(3);
    } else {
      sol.push_back(INF);
      sol.push_back(-1);
      sol.push_back(INF + 1);
      sol.push_back(-2);
    }
  }
  return norm(sol);
}

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