Submission #675994

#	Time	Username	Problem	Language	Result	Execution time	Memory
675994		Essa2006	Permutation (APIO22_perm)	C++17	0 / 100	1 ms	212 KiB

perm

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
ll mx, K;
vector<int>Ans;
void solve(){
    vector<int>AAns;
    bitset<1000>a=K;
        int group=0;
        for(int i=0;i<=64;i++){
            if(a[i]){
                group++;
                for(int j=0;j<i;j++)
                    AAns.push_back(j);
            }
        }
        vector<int>Old=AAns;
        int n=AAns.size(), cur=0;
        for(int i=n-1;i>=0;i--){
            if(!Old[i]){
                int ind=i;
                while(true){
                    AAns[ind]=cur++;
                    if(ind<n-1 && Old[ind+1])
                        ind++;
                    else
                        break;
                }
            }
        }
        group--;
        for(int i=0;i<AAns.size();i++)
            AAns[i]+=mx;
        mx+=cur;
        for(int i=0;i<Ans.size();i++){
            AAns.push_back(Ans[i]);
        }
        Ans=AAns;
        if(group>1){
            K=group+1;
            solve();
        }
        else if(group){
            int s=mx;
            for(int i=0;i<Ans.size();i++){
                swap(Ans[i], s);
            }
            Ans.push_back(s);
        }
            
}
vector<int> construct_permutation(ll k){
    K=k;
    mx=0;
    Ans.clear();
    solve();
    vector<int>parts;
    int cur=0;
    for(int i=0;i<Ans.size();i++){
        cur++;
        if(i==Ans.size()-1 || Ans[i+1]<Ans[i])
            parts.push_back(cur), cur=0;
    }
    sort(all(parts));
    int now=1;
    int mx=1e9;
    cur=0;
    int ind=0;
    int mxind=0;
    for(int i=0;i<Ans.size() && ind<parts.size();i++){
        if(now==parts[ind]){
            ind++;
            Ans[i]=cur++;
            mxind=i;
        }
        else{
            Ans[i]=mx--;
            now++;
        }
    }
    mxind++;
    while(Ans.size()>mxind)
        Ans.pop_back();
    reverse(all(Ans));
    int mn=1e9;
    for(int i=0;i<Ans.size();i++){
        if(Ans[i]>=cur)
            mn=min(mn, Ans[i]);
    }
    for(int i=0;i<Ans.size();i++){
        if(Ans[i]>=cur)
            Ans[i]-=mn-cur;
    }
    return Ans;
}

Compilation message (stderr)

perm.cpp: In function 'void solve()':
perm.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i=0;i<AAns.size();i++)
      |                     ~^~~~~~~~~~~~
perm.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i=0;i<Ans.size();i++){
      |                     ~^~~~~~~~~~~
perm.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int i=0;i<Ans.size();i++){
      |                         ~^~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<Ans.size();i++){
      |                 ~^~~~~~~~~~~
perm.cpp:66:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if(i==Ans.size()-1 || Ans[i+1]<Ans[i])
      |            ~^~~~~~~~~~~~~~
perm.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<Ans.size() && ind<parts.size();i++){
      |                 ~^~~~~~~~~~~
perm.cpp:75:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<Ans.size() && ind<parts.size();i++){
      |                                 ~~~^~~~~~~~~~~~~
perm.cpp:87:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |     while(Ans.size()>mxind)
      |           ~~~~~~~~~~^~~~~~
perm.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<Ans.size();i++){
      |                 ~^~~~~~~~~~~
perm.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<Ans.size();i++){
      |                 ~^~~~~~~~~~~

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