結果
問題 | 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 1000000001int 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;}