oj.uz

Submission #591754

# Submission time Handle Problem Language Result Execution time Memory
591754 2022-07-07T20:22:12 Z keta_tsimakuridze Permutation (APIO22_perm) C++17
10 / 100
 1 ms 340 KB 
#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> x;
map<int,int> id;
/*
5
7
5
15
17
20
*/
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;
	for(int i = b; i >= 1; i -= 2) {
        int b1 = k & (1ll << i);
        int 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:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  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 1 ms 296 KB Output is correct

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -