Submission #574184

#TimeUsernameProblemLanguageResultExecution timeMemory
574184LawlietPermutation (APIO22_perm)C++17
92.67 / 100
2 ms340 KiB
#include "perm.h" #include <bits/stdc++.h> using namespace std; vector<int> buildBaseTwo(long long k) { int mn = 0; vector<int> ans; while( k > 1 ) { if( k & 1 ) ans.push_back( mn++ ), k ^= 1; else ans.push_back( -1 ), k >>= 1; } int mx = (int)ans.size() - 1; for(int i = 0 ; i < ans.size() ; i++) if( ans[i] == -1 ) ans[i] = mx--; reverse( ans.begin() , ans.end() ); return ans; } vector<int> buildBaseThree(long long k) { int mn = 0; vector<int> ans; while( k > 2 ) { if( k%3 == 1 ) ans.push_back( mn++ ), k--; else if( k%3 == 2 ) ans.insert( ans.end() , { mn , mn + 1 } ), k -= 2, mn += 2; else ans.insert( ans.end() , { -1 , -1 } ), k /= 3; } if( k == 2 ) ans.push_back( mn++ ); int mx = (int)ans.size() - 1; for(int i = 0 ; i < ans.size() ; i++) if( ans[i] == -1 ) ans[i + 1] = mx--, ans[i] = mx--; reverse( ans.begin() , ans.end() ); return ans; } vector<int> buildBaseFive(long long k) { int mn = 0; vector<int> ans; while( k > 4 ) { if( k%5 == 0 ) ans.insert( ans.end() , { -1 , -1 , -1 } ), k /= 5; else if( k%5 == 1 ) ans.insert( ans.end() , { mn++ } ), k--; else if( k%5 == 2 ) ans.insert( ans.end() , { mn , mn + 1 } ), k -= 2, mn += 2; else if( k%5 == 3 ) ans.insert( ans.end() , { mn + 1 , mn } ), k -= 3, mn += 2; else ans.insert( ans.end() , { mn , mn + 2 , mn + 1 } ), k -= 4, mn += 3; } if( k == 2 ) ans.push_back( mn++ ); if( k == 3 ) ans.insert( ans.end() , { mn , mn + 1 } ); if( k == 4 ) ans.insert( ans.end() , { mn + 1 , mn } ); int mx = (int)ans.size() - 1; for(int i = 0 ; i < ans.size() ; i++) if( ans[i] == -1 ) ans[i + 1] = mx--, ans[i + 2] = mx--, ans[i] = mx--; reverse( ans.begin() , ans.end() ); return ans; } vector<int> construct_permutation(long long k) { vector<int> bases[] = { buildBaseTwo(k), buildBaseThree(k), buildBaseFive(k) }; sort( bases , bases + 3 , [&](vector<int>& a, vector<int>& b){ return a.size() < b.size(); }); return bases[0]; }

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> buildBaseTwo(long long int)':
perm.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0 ; i < ans.size() ; i++)
      |                  ~~^~~~~~~~~~~~
perm.cpp: In function 'std::vector<int> buildBaseThree(long long int)':
perm.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0 ; i < ans.size() ; i++)
      |                  ~~^~~~~~~~~~~~
perm.cpp: In function 'std::vector<int> buildBaseFive(long long int)':
perm.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i = 0 ; i < ans.size() ; i++)
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...