oj.uz

Submission #584015

# Submission time Handle Problem Language Result Execution time Memory
584015 2022-06-26T16:30:37 Z YassineBenYounes Permutation (APIO22_perm) C++17
71.2154 / 100
 13 ms 1364 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
61.215384618 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 340 KB Partially correct
5 Partially correct 5 ms 596 KB Partially correct
6 Partially correct 6 ms 596 KB Partially correct
7 Partially correct 8 ms 852 KB Partially correct
8 Partially correct 12 ms 1048 KB Partially correct
9 Correct 1 ms 340 KB Output is correct
10 Partially correct 13 ms 1364 KB Partially correct
11 Partially correct 10 ms 980 KB Partially correct
12 Partially correct 9 ms 932 KB Partially correct
13 Partially correct 10 ms 980 KB Partially correct