Submission #572776

#	Time	Username	Problem	Language	Result	Execution time	Memory
572776		benson1029	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	368 KiB

perm

#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 (stderr)

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 / 10
• Subtask 2: 90 / 90