Submission #591758

#	Time	Username	Problem	Language	Result	Execution time	Memory
591758		keta_tsimakuridze	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	340 KiB

perm

#include "perm.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> x;
map<int,int> id;
/*
5
100000000000000
*/
void add(int a) {
    x.push_back(a);
    id[a] = (int)x.size() - 1;
}
std::vector<int> construct_permutation(long long k)
{
    x.clear();
    int l = 0, r = -1;
    int b = 0;
    for(int i = 0; i < 60; i++) if(k & (1ll << i)) b = i;
    --b;
  //  cout << b << endl;
	for(int i = b; i >= 1; i -= 2) {
        ll b1 = k & (1ll << i);
        ll b2 = k & (1ll << (i - 1));
        if(!b1 && !b2) {
            add(++r);
            add(++r);
            continue;
        }
        if(b1 && !b2) {
            add(++r);
            add(--l);
            add(++r);

            continue;
        }
        if(b2 && !b1) {
            add(++r);
            add(++r);
            add(--l);
            continue;
        }

        if(i != b && id[l] > id[l + 1]) {
            add(++r);
            add(++r);

            x[id[l]] = l - 1; id[l - 1] = id[l];
            x[id[l + 1]] = l; id[l] = id[l + 1];
            add(l + 1);
            --l;
            continue;
        }
        add(++r);
        add(--l);
        add(++r);
        add(--l);
	}
	if(b % 2 == 0) {
        if(k % 2 == 0) add(++r);
        else add(++r), add(--l);
	}
	for(int i = 0; i < x.size(); i++) x[i] += -l;
	return x;
}

Compilation message (stderr)

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

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