답안 #584015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584015	2022-06-26T16:30:37 Z	YassineBenYounes	순열 (APIO22_perm)	C++17	71.2154 / 100	13 ms	1364 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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