Submission #1140228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140228		Sang	Permutation (APIO22_perm)	C++17	0 / 100	1093 ms	320 KiB

perm

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;


map<int, int> dist;
queue<int> q[95];

vector<int> construct_permutation_sub(long long k){
   --k;
   q[0].push(k);
   dist[k] = 0;
   FOR (i, 0, 90){
        while (!q[i].empty()){
            int x = q[i].front(); q[i].pop();
            if (dist[x] != i) continue;
            FOR (j, 1, 60){
                if ((1<<j) - 1 > x || i + j > 90) break;
                int nxt = x - (1<<j) + 1;
                if (dist.find(nxt) == dist.end() || dist[nxt] > i + j){
                    dist[nxt] = i + j;
                    q[i + j].push(nxt);
                }
            }
        }
   }
   vi bit;
   int s = dist[0] - 1;
   int cur = 0;
   while (cur != k){
        FOR (j, 1, 60){
            if ((1<<j) - 1 + cur > k) continue;
            int nxt = cur + (1<<j) - 1;
            if (dist.find(nxt) == dist.end()) continue;
            if (dist[nxt] + j == dist[cur]){
                bit.pb(j);
                cur = nxt;
                break;
            }
        }
    }
    vi ans;
    for (int &x : bit){
        FOR (i, s - x + 1, s) ans.pb(i);
        s -= x;
    }
    return ans;

}

vector<int> construct_permutation(long long k){
    if (k <= 5000) return construct_permutation_sub(k);
    vi bit, ans;
    int s = 0, cnt = 0;
    k--;
    while (k){
        FORD(i, 60, 1){
            if (k < (1ll<<i) -1 ) continue;
            k -= (1ll<<i) - 1;
            s += i;
            bit.pb(i);
            break;
        }
    }
    --s;
    for (int &x : bit){
        FOR (i, s - x + 1, s){
            ans.pb(i);
        }
        s -= x;
    }
    return ans;
}

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