Submission #738982

#	Time	Username	Problem	Language	Result	Execution time	Memory
738982		Prieved1	Permutation (APIO22_perm)	C++17	91.33 / 100	4 ms	340 KiB

perm

#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> construct_permutation(long long k)
{
  vector<int> v;
  {
    long long tmp=2;
    while(tmp<=k) {
      v.push_back(v.size());
      tmp*=2;
    }
    k-=tmp/2;
  }
  cerr << v.size() << endl;
  vector<int> add;
  vector<long long> b4;
  while(k>0) {
    b4.push_back(k%4);
    k/=4;
  }
  map<int,int> mp;
  for(int i =0;i<(int)b4.size();i++) {
    if(b4[i]==0)continue;
    else if(b4[i]==1) {
      mp[2*i]++;
    }
    else if(b4[i]==2) {
      mp[2*i+1]++;
    }
    else {
      mp[2*i+1]++;
      mp[2*i]++;
    }
  }
  for(int i = 0;i<=100;i++) {
    int c=mp[i]/2;
    mp[i]%=2;
    if(mp[i])add.push_back(i);
    mp[i+1]+=c;
  }
  reverse(add.begin(),add.end());
  for(int i:add) {
    v.insert(v.begin()+i,v.size());
  }
	return v;
}

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