oj.uz

Submission #789749

# Submission time Handle Problem Language Result Execution time Memory
789749 2023-07-21T23:54:34 Z tvladm2009 Permutation (APIO22_perm) C++17
100 / 100
 11 ms 360 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 5 ms 360 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 11 ms 360 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 10 ms 340 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 9 ms 304 KB Output is correct
13 Correct 10 ms 340 KB Output is correct