Submission #852967

#	Time	Username	Problem	Language	Result	Execution time	Memory
852967		adhityamv	Permutation (APIO22_perm)	C++17	0 / 100	0 ms	344 KiB

perm

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> construct_permutation(ll k){
    ll pow4[30]={};
    pow4[0]=1;
    for(int i=1;i<30;i++) pow4[i]=pow4[i-1]*4LL;
    vector<int> qnry;
    int e=29;
    while(pow4[e]>k) e--;
    while(e>=0){
        qnry.push_back(k/pow4[e]);
        k%=pow4[e];
        e--;
    }
    vector<int> ans;
    bool fxd=false;
    int m=(int) qnry.size();
    int mx=0;
    int mn=-1;
    int smpos=-1;
    int ind=0;
    if(qnry[0]==2){
        ans.push_back(0);
        ind++;
        mx=1;
        smpos=0;
    }
    if(qnry[0]==3){
        ans.push_back(1);
        ans.push_back(0);
        ind+=2;
        mx=2;
        smpos=1;
        fxd=true;
    }
    for(int i=1;i<m;i++){
        if(qnry[i]<=1){
            ans.push_back(mx);
            ans.push_back(mx+1);
            mx+=2;
            ind+=2;
            if(qnry[i]==1){
                smpos=ind;
                ans.push_back(mn);
                ind++;
                mn--;
                fxd=true;
            }
        }
        if(qnry[i]==2){
            ans.push_back(mx);
            smpos=ind+1;
            ans.push_back(mn);
            mn--;
            ans.push_back(mx+1);
            ind+=3;
            mx+=2;
            fxd=true;
        }
        if(qnry[i]==3){
            if(!fxd){
                ans.push_back(mx);
                ans.push_back(mn);
                mn--;
                ans.push_back(mx+1);
                mx+=2;
                smpos=ind+3;
                ans.push_back(mn);
                mn--;
                ind+=4;
                fxd=true;
            } else{
                ans.push_back(mx);
                ans.push_back(mn+1);
                ans.push_back(mx+1);
                ind+=3;
                ans[smpos]--;
                mn--;
            }
        }
    }
    for(int i=0;i<ans.size();i++) ans[i]-=(mn+1);
    return ans;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<ans.size();i++) ans[i]-=(mn+1);
      |                 ~^~~~~~~~~~~

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