結果
問題 |
No.326 あみだますたー
|
ユーザー |
![]() |
提出日時 | 2019-04-11 08:35:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,972 bytes |
コンパイル時間 | 969 ms |
コンパイル使用メモリ | 111,436 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 05:08:57 |
合計ジャッジ時間 | 2,253 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include<algorithm> #include<complex> #include<ctype.h> #include<iomanip> #include<iostream> #include<fstream> #include<map> #include<math.h> #include<numeric> #include<queue> #include<set> #include<stack> #include<stdio.h> #include<string> #include<string> #include<vector> using namespace std; typedef long long ll; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)<<endl #define p2(s, t) cout << (s) << " " << (t) << endl #define br() p("") #define pn(s) cout << (#s) << " " << (s) << endl #define p_yes() p("Yes") #define p_no() p("No") const ll mod = 1e9 + 7; const ll inf = 1e18; template < typename T > void vprint(T &V){ for(auto v : V){ cout << v << " "; } cout << endl; } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N, K; cin >> N >> K; vector<ll> B(N); FOR(i, 0, N){ B[i] = i; } FOR(i, 0, K){ ll x, y; cin >> x >> y; x--; y--; swap(B[x], B[y]); } vector<ll> A(N); FOR(i, 0, N){ cin >> A[i]; A[i]--; } // index 逆引き map<ll, ll> mp; FOR(i, 0, N){ mp[A[i]] = i; } vector<ll> C(N); FOR(i, 0, N){ C[i] = mp[i]; } map<ll, ll> mp_v_to_i; FOR(i, 0, N){ mp_v_to_i[C[i]] = i; } // vprint(C); vector<ll> D(N); FOR(i, 0, N){ ll v = B[i]; D[i] = mp_v_to_i[v]; } // vprint(D); vector<pair<ll, ll> > swaps; // Dをバブルソートする問題になった FOR(i, 0, N-1){ bool swapped = false; for(int j=0; j<N-1-i; j++){ if(D[j]>D[j+1]){ swap(D[j], D[j+1]); swapped = true; swaps.push_back(make_pair(j, j+1)); } } if(!swapped) break; } p(swaps.size()); for(auto p : swaps){ p2(p.first+1, p.second+1); } return 0; }