제출 #975697

#제출 시각아이디문제언어결과실행 시간메모리
975697ShaShi순열 (APIO22_perm)C++17
91.33 / 100
9 ms448 KiB
#include "perm.h" #include <bits/stdc++.h> #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define pii pair<int, int> using namespace std; typedef long long ll; const int MAXN = (int)1e6 + 7; const int LG = 60; vector<int> solve1(ll k) { vector<int> res; bool flag = 0; for (int i=LG-1; i>=0; i--) { if (!(k&(1ll<<i))) continue; if (!flag) { for (int j=1; j<=i; j++) res.pb(j); flag = 1; continue; } for (int j=0; j<res.size(); j++) if (res[j] >= i+1) res[j]++; res.pb(i+1); } // for (int i=0; i<res.size(); i++) res[i]--; return res; } vector<int> solve2(ll k) { vector<int> res = solve1(k+1); if (k >= 2 && (k%2) == 0) { vector<int> res2 = solve2((k-2)/2); if (res2.size()+2 < res.size()) { int mx=1; for (int i=0; i<res2.size(); i++) mx = max(mx, ++res2[i]); res2.pb(mx+1); res2.pb(1); swap(res, res2); } } // if (k > 0) { // vector<int> res2 = solve2(k-1); // if (res2.size()+1 < res.size()) { // for (int i=0; i<res2.size(); i++) res2[i]++; // res2.pb(1); // swap(res, res2); // } // } if (k > 0 && (k%2) == 1) { vector<int> res2 = solve2((k-1)/2); if (res2.size()+1 < res.size()) { int mx = 0; for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]); res2.pb(mx+1); swap(res, res2); } } // if (k >= 2 && ((k-2)%3) == 0) { // vector<int> res2 = solve2((k-2)/3); // if (res2.size()+2 < res.size()) { // int mx = 0; // for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]); // res2.pb(mx+2); res2.pb(mx+1); // swap(res, res2); // } // } // if (k >= 3 && ((k-3)%4) == 0) { // vector<int> res2 = solve2((k-3)/4); // if (res2.size()+2 < res.size()) { // int mx = 0; // for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]); // res2.pb(mx+1); res2.pb(mx+2); // swap(res, res2); // } // } return res; } vector<int> construct_permutation(ll k) { // vector<int> res1 = solve1(k); // if (res1.size() <= 90) return res1; vector<int> res2 = solve2(k-1); for (int i=0; i<res2.size(); i++) res2[i]--; return res2; } // int main() { // ll n = (1ll<<18)-3; // // ll n = 511; // vector<int> res = construct_permutation(n); // cout << res.size() << endl; // for (int i:res) cout << i << " "; // return 0; // }

컴파일 시 표준 에러 (stderr) 메시지

perm.cpp: In function 'std::vector<int> solve1(ll)':
perm.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int j=0; j<res.size(); j++) if (res[j] >= i+1) res[j]++;
      |                 ~^~~~~~~~~~~
perm.cpp: In function 'std::vector<int> solve2(ll)':
perm.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int i=0; i<res2.size(); i++) mx = max(mx, ++res2[i]);
      |                  ~^~~~~~~~~~~~
perm.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);
      |                  ~^~~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(ll)':
perm.cpp:121:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for (int i=0; i<res2.size(); i++) res2[i]--;
      |                ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...