| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1045108 | amine_aroua | Parrots (IOI11_parrots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #include "encoder.h"
// #include "encoderlib.h"
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 64;
cpp_int fact[MAXN + 1];
void calc_fact()
{
fact[0] = 1;
for(ll i = 1 ; i <= 16 ; i++)
{
fact[i] = fact[i - 1] * i;
}
}
cpp_int find_code(int n , vector<int> perm)
{
calc_fact();
cpp_int code = 0;
for(int i = 0 ; i <n ;i++)
{
int smaller = 0;
for(int j = i + 1; j < n ;j++)
{
smaller+=(perm[j] < perm[i]);
}
code+=fact[n - i - 1] * smaller;
}
return code;
}
void encode(int N, int M[])
{
map<int , int> compress;
vector<int> cur;
for(int i = 0 ;i < N ; i++)
{
cur.push_back(M[i]);
// send(M[i]);
// send(M[i]);
}
sort(cur.begin() , cur.end());
for(int i = 0 ; i < N ; i++)
{
compress[cur[i]] = i;
}
vector<int> perm(N);
for(int i = 0 ; i < N ; i++)
{
perm[i] = compress[M[i]];
}
cpp_int code = find_code(N , perm);
int cnt = 1;
while(code)
{
int r = code%10;
// send(cnt * 10 + r);
cnt++;
code/=10;
}
}
int main()
{
int n ;
cin>>n;
int m[n];
for(int i = 0 ; i <n ;i++)
cin>>m[i];
encode(n , m);
}#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 16;
ll fact[MAXN + 1];
void calc_fact()
{
fact[0] = 1;
for(ll i = 1 ; i <= 16 ; i++)
{
fact[i] = fact[i - 1] * i;
}
}
vector<int> find_perm(int n , ll code)
{
calc_fact();
vector<int> nums;
for(int i = 0 ; i < n ; i++)
{
nums.push_back(i);
}
vector<int> perm;
for(int i = 1 ; i <= n; i++)
{
ll idx = code / fact[n - i];
perm.push_back(nums[idx]);
nums.erase(nums.begin() + idx);
code-=idx * fact[n - i];
}
return perm;
}
void decode(int N, int L, int X[])
{
vector<int> vals;
map<int ,int> occ;
for(int i = 0 ; i < L ; i++)
{
occ[X[i]]++;
}
for(int i = 0 ; i < L ; i++)
{
if(occ[X[i]] >= 2)
{
vals.push_back(X[i]);
occ[X[i]]-=2;
}
}
sort(vals.begin(), vals.end());
ll code = 0;
for(auto p : occ)
{
if(p.second == 1)
{
int x = p.first;
ll d = x%10;
x/=10;
code+=d * (ll)pow(10 , x - 1);
}
}
vector<int> perm = find_perm(N , code);
for(auto &x : perm)
{
output(vals[x]);
}
}