Submission #1045101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045101		amine_aroua	Parrots (IOI11_parrots)	C++17	52 / 100	2 ms	1324 KiB

encoder

#include "encoder.h"
#include "encoderlib.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;
    }
}
ll find_code(int n , vector<int> perm)
{
    calc_fact();
    ll 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]];
    }
    ll code = find_code(N , perm);
    int cnt = 1;
    while(code)
    {
        int r = code%10;
        send(cnt * 10 + r);
        cnt++;
        code/=10;
    }
}

decoder

#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]);
    }
    
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 29
• Subtask 5: 0 / 19