結果
問題 | No.1854 Limited Bubble Sort |
ユーザー |
![]() |
提出日時 | 2022-02-25 22:40:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 4,748 ms |
コンパイル使用メモリ | 252,420 KB |
最終ジャッジ日時 | 2025-01-28 02:17:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define Inf 1000000001 int main(){ int _t; cin>>_t; rep(_,_t){ int n; cin>>n; vector<int> p(n); rep(i,n){ cin>>p[i]; p[i]--; } bool f = true; vector<int> a; rep(i,n){ int ind = 0; rep(j,n){ if(p[j]==i){ ind = j; break; } } while(ind!=i){ int cur = ind-1; bool F = false; while(true){ if(cur==-1 || p[cur] < i){ F = true; break; } if(cur==p[cur]){ f = false; break; } if(cur+1 == p[cur])cur--; else break; } if(!f)break; //cout<<cur<<endl; if(F){ while(p[i] != i){ a.push_back(ind-1); swap(p[ind],p[ind-1]); ind--; } } else{ while(cur!=ind){ a.push_back(cur); swap(p[cur],p[cur+1]); cur++; } ind--; } } if(!f)break; } if(!f){ cout<<-1<<endl; } else{ /* rep(i,n)cout<<p[i]<<','; cout<<endl; */ //assert(a.size()<=n*n); cout<<a.size()<<endl; rep(i,a.size()){ if(i!=0)cout<<' '; cout<<a[i]+1; } cout<<endl; } } return 0; }