結果
問題 | No.1854 Limited Bubble Sort |
ユーザー |
![]() |
提出日時 | 2022-02-25 22:10:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,795 bytes |
コンパイル時間 | 2,490 ms |
コンパイル使用メモリ | 198,868 KB |
最終ジャッジ日時 | 2025-01-28 02:07:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; void solve() { int n; cin >> n; vector<int> p(n); REP(i, n) cin >> p[i], --p[i]; vector<int> a; auto op = [&](int ai) -> void { a.emplace_back(ai); swap(p[ai], p[ai + 1]); }; for (int i = 0; i < n;) { int j = i; while (j < n && p[j] != j) ++j; FOR(k, i, j) { if (p[k] < i || j <= p[k]) { cout << "-1\n"; return; } } FOR(k, i, j) { for (int pos = (find(p.begin() + i, p.begin() + j, k) - p.begin()) - 1; pos >= k; --pos) { int l = pos; while (l >= k && p[l] == l + 1) --l; if (l < k) { for (; pos >= k; --pos) op(pos); } else { for (; l <= pos; ++l) op(l); } } } i = j + 1; } const int q = a.size(); cout << q << '\n'; REP(i, q) cout << a[i] + 1 << " \n"[i + 1 == q]; } int main() { int t; cin >> t; while (t--) solve(); return 0; }