Submission #1065680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065680		stdfloat	Permutation (APIO22_perm)	C++17	100 / 100	3 ms	508 KiB

perm

#include <bits/stdc++.h>
#include "perm.h"
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;
        // cout << "i x " << i << ' ' << x << endl << "v ";
        // for (auto i : v) {
        //     cout << i << ' ';
        // }
        // cout << endl;
        if (!i) {
            v.push_back(++mx);
            if (x) v.push_back(--mn);
            break;
        }

        bool y = (k >> (i - 1)) & 1;
    
        // cout << "y " << y << endl;

        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.0005 / (int)v.size());
            }
        }

        i--;
        tr1 = true;
    }

    // for (auto i : v) {
    //     cout << i << ' ';
    // }
    // cout << endl;

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

    // for (auto i : ans) {
    //     cout << i << ' ';
    // }
    // cout << endl;

    return ans;
}

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