Submission #658614

#	Time	Username	Problem	Language	Result	Execution time	Memory
658614		zglicz	Permutation (APIO22_perm)	C++17	93.33 / 100	2 ms	340 KiB

perm

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <random>
#include <cmath>
#include <chrono>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <climits>
#include <stack>
#include <valarray>
#include <random>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define trav(a, x) for(auto& a : x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;
template<typename T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b){return b>a?a=b,1:0;}

#include "perm.h"

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(char c) {
  return string(1, c);
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


// #include <atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353; // modint1000000007;
// typedef vector<mint> vmi;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use rng() to get unsigned int
// mt19937_64 for random long longs

int f(ll val) {
  if (val == 2) return 1;
  if (val == 1) return 0;
  if (val % 3 == 0) return 2 + f(val / 3);
  if (val % 2 == 0) return 1 + f(val / 2);
  return 1 + f(val - 1);
}
const ll inf = 1e18;
static bool check_permutation(vector<int> v)
{
  sort(v.begin(),v.end());
  for(int i=0;i<v.size();i++)
    if(v[i]!=i) return 0;
  return 1;
}

long long count_increasing(const vector<int>& v) {
  vector<long long> dp(v.size() + 1, 0);
  dp[0] = 1;
  for (int x : v)
  {
    for (int i = 0; i <= x; i++)
    {
      dp[x+1] += dp[i];
      dp[x+1] = min(dp[x+1],inf+1);
    }
  }
  long long result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
    result += dp[i];
    result = min(result,inf+1);
  }
  return result;
}

vi construct_permutation(ll k) {
  int ile = f(k);
  debug(ile);
  vi ans(ile);
  int p = 0, q = ile - 1;
  int nasSmall = 0, nasBig = ile - 1;
  while (true) {
    debug(k, p, q, nasSmall, nasBig);
    if (k == 2) {
      ans[p] = nasSmall;
      break;
    } else if (k == 1) {
      break;
    } else if (k % 3 == 0) {
      k /= 3;
      ans[p++] = nasSmall + 1;
      ans[p++] = nasSmall;
      nasSmall += 2;
    } else if (k % 2 == 0) {
      ans[q--] = nasBig--;
      k /= 2;
    } else {
      --k;
      ans[p++] = nasBig--;
    }
  }
  return ans;
}

// int main() {
// 	ios_base::sync_with_stdio(false); cin.tie(0);
// 	int t;
// 	// cin >> t;
// 	// t = 1;
//   ll k;
//   cin >> k;
//   auto ans = construct_permutation(k);
//   cout << sz(ans) << endl;
//   for (auto a : ans) {
//     cout << a << ' ';
//   }
//   cout << endl;
//   assert(count_increasing(ans) == k);
//   assert(check_permutation(ans));
// 	// while (t--) {
// 	// 	solve();
// 	// }
// }

Compilation message (stderr)

perm.cpp: In function 'bool check_permutation(std::vector<int>)':
perm.cpp:156:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |   for(int i=0;i<v.size();i++)
      |               ~^~~~~~~~~
perm.cpp: In function 'vi construct_permutation(ll)':
perm.cpp:133:20: warning: statement has no effect [-Wunused-value]
  133 | #define debug(...) 42
      |                    ^~
perm.cpp:182:3: note: in expansion of macro 'debug'
  182 |   debug(ile);
      |   ^~~~~
perm.cpp:133:20: warning: statement has no effect [-Wunused-value]
  133 | #define debug(...) 42
      |                    ^~
perm.cpp:187:5: note: in expansion of macro 'debug'
  187 |     debug(k, p, q, nasSmall, nasBig);
      |     ^~~~~
perm.cpp: At global scope:
perm.cpp:153:13: warning: 'bool check_permutation(std::vector<int>)' defined but not used [-Wunused-function]
  153 | static bool check_permutation(vector<int> v)
      |             ^~~~~~~~~~~~~~~~~

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