Submission #572594

#	Time	Username	Problem	Language	Result	Execution time	Memory
572594		arthur_nascimento	Permutation (APIO22_perm)	C++17	Compilation error	0 ms	0 KiB

perm

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
using namespace std;


#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
#include <stdlib.h>

using namespace std;

static long long MX=1e18;

static bool check_permutation(vector<int> v)
{
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
		if(v[i]!=i) return 0;
	return 1;
}

long long count_increasing(const vector<int>& v) {
  vector<long long> dp(v.size() + 1, 0);
  dp[0] = 1;
  for (int x : v)
  {
  	for (int i = 0; i <= x; i++)
  	{
  		dp[x+1] += dp[i];
  		dp[x+1] = min(dp[x+1],MX+1);
  	}
  }
  long long result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  	result = min(result,MX+1);
  }
  return result;
}

int main() {
	int t;
	assert(1 == scanf("%d", &t));
	while(t--)
	{
		long long k;
		assert(1 == scanf("%lld",&k));
		vector<int> ret=construct_permutation(k);
		if(!check_permutation(ret))
		{
			printf("WA: Returned array is not a permutation\n");
			exit(0);
		}
		long long inc=count_increasing(ret);
		if(inc!=k)
		{
			if(inc==MX+1)
				printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
			else
				printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
			exit(0);
		}
		printf("%d\n",(int)ret.size());
		for(int i=0;i<ret.size();i++)
		{
			printf("%d",ret[i]);
			if(i+1==ret.size())
				printf("\n");
			else
				printf(" ");
		}
	}
	return 0;
}


std::vector<int> construct_permutation(long long k)
{
	
    //k++;
    ll aux = k, sz = 0;
    
    while(aux)
        aux /= 2, sz++;
        
        
    vector<pii> ans;
    
    for(int i=0;i<sz-1;i++)
        ans.pb({2*i,i+1});
        
    vector<int> dec;
    dec.pb(1);
    
    int x = 1, y = 0, skip = 0;
    
    for(int i=sz-2;i>=0;i--, x += 2, y--){
        
        if((k & (1ll << i)) == 0) continue;
        
        if(skip){
            skip = 0;
            ans.pb({x,dec[dec.size()-2]+1});
            continue;
        }
        
        
        if(dec.size() == 1 || i == 0 || (k & (1ll << (i-1))) == 0){
            
            ans.pb({x,y});
            dec.pb(y);
            
            
        }
        
        else {
    
            skip = 1;
            
        }
        
        
        
    }

    sort(ans.begin(), ans.end());
    
    int c = 0;
    for(auto &p : ans)  p.first = c++;
    
    c = 0;
    sort(ans.begin(), ans.end(), [](pii i,pii j){
        if(i.second == j.second) return i.first > j.first;
        return i.second < j.second;
    });
    
    for(auto &p : ans)  p.second = c++;
    
    sort(ans.begin(), ans.end());

	vector<int> r;
	for(auto p : ans)
		r.pb(p.second);

    return r;

}

Compilation message (stderr)

perm.cpp: In function 'bool check_permutation(std::vector<int>)':
perm.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~
perm.cpp: In function 'int main()':
perm.cpp:53:19: error: 'construct_permutation' was not declared in this scope; did you mean 'check_permutation'?
   53 |   vector<int> ret=construct_permutation(k);
      |                   ^~~~~~~~~~~~~~~~~~~~~
      |                   check_permutation
perm.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int i=0;i<ret.size();i++)
      |               ~^~~~~~~~~~~
perm.cpp:72:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    if(i+1==ret.size())
      |       ~~~^~~~~~~~~~~~