Submission #1065687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065687		stdfloat	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	372 KiB

perm

#include <bits/stdc++.h>
#include "perm.h"
// #include "grader.cpp"
using namespace std;

using ll = long long;

vector<int> construct_permutation(ll k) {
    bool tr1 = false, tr2 = false;
    int mn = 0, smn = 0, mx = -1;
    vector<double> v;
    for (int i = 59; i >= 0; i--) {
        if (!tr1 && !((k >> i) & 1)) continue;

        bool x = (k >> i) & 1;
        if (!i) {
            v.push_back(++mx);
            if (x) v.push_back(--mn);
            break;
        }

        bool y = (k >> (i - 1)) & 1;
    
        if (!x && !y) {
            v.push_back(++mx);
            v.push_back(++mx);

            if (!tr1) smn = 1;
        }
        else if (!x) {
            v.push_back(++mx);
            v.push_back(++mx);
            smn = mn;
            v.push_back(--mn);
        
            tr2 = true;
        }
        else if (!y) {
            if (tr1) {
                v.push_back(++mx);
                smn = mn;
                v.push_back(--mn);
                tr2 = true;
            }
            
            v.push_back(++mx);
        }
        else {
            if (!tr1) {
                v.push_back(++mx);
                smn = 0;
                v.push_back(--mn);
                tr2 = true;
            }
            else if (!tr2) {
                v.push_back(++mx);
                v.push_back(++mx);
                v.push_back(mn + 0.5);
                smn = mn;
                v.push_back(--mn);

                tr2 = true;
            }
            else {
                v.push_back(++mx);
                v.push_back(++mx);
                v.push_back(smn + 0.5 / (int)v.size());
            }
        }

        i--;
        tr1 = true;
    }

    int x = 0;
    map<double, int> m;
    for (auto i : v) {
        m[i] = 1;
    }
    for (auto &i : m) {
        i.second = x++;
    }

    vector<int> ans;
    for (auto i : v) {
        ans.push_back(m[i]);
    }

    return ans;
}

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