Submission #1049329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049329		SN0WM4N	Permutation (APIO22_perm)	C++17	10 / 100	1 ms	348 KiB

perm

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

#pragma GCC optimize("O3")

#ifdef LOCAL 
        #include "debug.h"
#else 
        #define dbg(...) 0
        #include "perm.h"
#endif

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 998244353; //[998244353, 1e9 + 7, 1e9 + 13]
const ld PI = acos(-1);
const ll NROOT = 800;

ll binpow(ll a, ll b, ll _MOD = -1) {
        if (_MOD == -1)
                _MOD = MOD;
        ll res = 1;
        for (; b; b /= 2, a *= a, a %= _MOD)
                if (b & 1) res *= a, res %= _MOD;
        return res;
}

void set_IO(string s) {
#ifndef LOCAL
        string in  = s +  ".in";
        string out = s + ".out";
        freopen(in.c_str(),  "r",  stdin);
        freopen(out.c_str(), "w", stdout);
#endif
}

bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}
ll invmod(ll a) {return binpow(a, MOD - 2);}

#define int long long 

vector<int32_t> construct_permutation(ll k) {
        int size = log2(k);

        vector<int32_t> ans;
        vector<int> aux;

        for (int i = 100; i >= 0; i --) 
                aux.push_back(10000 - i);

        k -= (1LL << size);
        for (int i = 0; i < size; i ++) {
                if (k & (1LL << i)) {
                        ans.push_back(aux.back());
                        aux.pop_back();
                }
                ans.push_back(i);
        }

        set<int> s;
        for (auto &x : ans)
               s.insert(x);

        int cnt = 0;

        map<int, int> ID;
        for (auto &x : s)
                ID[x] = cnt ++;
        for (auto &x : ans) {
                x = ID[x];
                if (x >= ans.size())
                        exit(1);
        }

        return ans;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 if (x >= ans.size())
      |                     ~~^~~~~~~~~~~~~
perm.cpp: In function 'void set_IO(std::string)':
perm.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(in.c_str(),  "r",  stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
perm.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(out.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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