oj.uz

Submission #591758

# Submission time Handle Problem Language Result Execution time Memory
591758 2022-07-07T20:26:25 Z keta_tsimakuridze Permutation (APIO22_perm) C++17
100 / 100
 2 ms 340 KB 
#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

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

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

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 272 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 296 KB Output is correct
13 Correct 2 ms 340 KB Output is correct