oj.uz

Submission #605436

# Submission time Handle Problem Language Result Execution time Memory
605436 2022-07-25T17:34:15 Z AugustinasJucas Permutation (APIO22_perm) C++17
91.3333 / 100
 11 ms 1500 KB 
#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> construct_permutation(long long k) {
    vector<int> RET(3000, 0);
    long long K = k;
    for(int H = 0; H < min(k-1, 90ll); H++){
        k = K - H;
        vector<int> init;
        int ind = 0;
        long long liko = 0;
        for(int i = 0; i < 64; i++) {
            long long bus = (1ll << i);
            if(bus > k) {
                // desim i-1 tu.
                for(int j = 0; j < i-1; j++) init.push_back(ind++);
                liko = k - (1ll << (i-1));
                break;
            }
        }
     //   cout << "liko = " << liko << ", popcnt = " << __builtin_popcount(liko) << endl;
        vector<int> ret;
        ind += __builtin_popcountll(liko) - 1 + H;
        for(int i = 0; i < H; i++) {
            ret.push_back(ind--);
        }
        for(int i = 0; i < init.size(); i++) {
            if((1ll << i) & liko) {
                ret.push_back(ind);
                ind--;
            }
            ret.push_back(init[i]);
        }
        if(ret.size() < RET.size()) {
            RET = ret;
        }
       // cout << "ret = "; for(auto x : ret) cout << x << " ";
        //cout << endl;
    }
    return RET;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Correct 8 ms 1364 KB Output is correct
5 Partially correct 9 ms 1492 KB Partially correct
6 Correct 9 ms 1468 KB Output is correct
7 Correct 9 ms 1440 KB Output is correct
8 Partially correct 11 ms 1412 KB Partially correct
9 Correct 9 ms 1492 KB Output is correct
10 Partially correct 10 ms 1492 KB Partially correct
11 Partially correct 10 ms 1492 KB Partially correct
12 Partially correct 11 ms 1500 KB Partially correct
13 Partially correct 10 ms 1492 KB Partially correct