oj.uz

Submission #572776

# Submission time Handle Problem Language Result Execution time Memory
572776 2022-06-05T09:16:19 Z benson1029 Permutation (APIO22_perm) C++17
100 / 100
 2 ms 368 KB 
#include "perm.h"
#include<bits/stdc++.h>
using namespace std;

std::vector<int> construct_permutation(long long k)
{
  if(k==2) return {0};
  else if(k==3) return {1, 0};
  else if(k==4) return {0, 1};
  else if(k==5) return {2, 0, 1};
  else if(k==6) return {0, 2, 1};
  else if(k==7) return {2, 1, 3, 0};
  else {
    vector<int> p = construct_permutation(k/4);
    if(k%4 == 0) { // *4
      p.push_back(p.size());
      p.push_back(p.size());
      return p;
    } else if(k%4==1) { // *4+1
      p.push_back(p.size());
      p.push_back(p.size());
      p.push_back(0);
      for(int i=p.size()-2; i>=0; i--) p[i]++;
      return p;
    } else if(k%4==2) { // *4+2
      for(int i=0; i<p.size(); i++) p[i]++;
      int t = p.size();
      p.push_back(t+1);
      p.push_back(0);
      p.push_back(t+2);
      return p;
    } else {
      int pos1 = -1, pos0 = -1;
      for(int i=0; i<p.size(); i++) {
        if(p[i]==1) pos1 = i;
        if(p[i]==0) pos0 = i;
      }
      if(pos1 < pos0 && pos1!=-1) {
        p.push_back(p.size());
        p.push_back(p.size());
        for(int i=0; i<p.size(); i++) if(p[i]>1) p[i]++;
        p.push_back(2);
        return p;
      } else {
        for(int i=0; i<p.size(); i++) p[i]+=2;
        int t = p.size()+2;
        p.push_back(t);
        p.push_back(1);
        p.push_back(t+1);
        p.push_back(0);
        return p;
      }
    }
  }
}

Compilation message

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

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 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 368 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct