Submission #584015

#	Time	Username	Problem	Language	Result	Execution time	Memory
584015		YassineBenYounes	Permutation (APIO22_perm)	C++17	71.22 / 100	13 ms	1364 KiB

perm

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
ll modd(ll x, ll n){while(x < 0){x += n;}return (x % n);} // modulo for negative numbers
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int msb(ll n){
    int i = 0;
    int last = 0;
    while(n > 0){
        if(n&1)last = i;
        n/=2;
        i++;
    }
    return last;
}

vector<int> construct_permutation(long long k){
     int i = 0;
     vl res;
     while(k > 0){
        ll wanted = k;
        if(i != 0)wanted++;
        ll found = msb(wanted);
        res.pb(found);
        k -= ((ll)1 << found);
        if(i !=0)k++;
        i++;
     }
     ll c = 0;
     for(int i = 0; i < res.size();i++){
        c += res[i];
     }
     vi v;
     for(int i = 0; i < res.size();i++){
        int x = c - res[i];
        for(int j = x; j< c;j++){
            v.pb(j);
        }
        c = x;
     }
     return v;
}

Compilation message (stderr)

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

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