結果
問題 | No.1888 Odd Insertion |
ユーザー |
![]() |
提出日時 | 2022-03-25 22:09:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 443 ms / 2,000 ms |
コード長 | 1,400 bytes |
コンパイル時間 | 3,859 ms |
コンパイル使用メモリ | 259,120 KB |
最終ジャッジ日時 | 2025-01-28 12:10:28 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#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 1000000001using P = pair<int,int>;P op(P a,P b){pair<int,int> r;r.first = max({a.first,b.first});r.second = r.first;if(a.first==r.second){r.second = max(a.second,b.first);}else{r.second = max(a.first,b.second);}return r;}P e(){return make_pair(0,0);}int main(){int n;cin>>n;vector<int> pos(n+2,0);fenwick_tree<int> F(n);set<int> S;rep(i,n){int pp;cin>>pp;//cin>>PP[i].first;S.insert(i+1);//PP[i].second = 0;pos[pp] = i;//F.add(i,1);}S.insert(n+1);vector<int> a,b;rep(i,n){auto it= S.begin();int r0 = *it;it++;int r1 = *it;int p0 = pos[r0];int p1= pos[r1];if(p0>p1){swap(p0,p1);swap(r0,r1);}int v0 = F.sum(0,p0);int v1 = F.sum(0,p1);//cout<<r0<<','<<r1<<','<<v0<<','<<v1<<endl;if(v1%2==0&&r1!=n+1){F.add(p1,1);a.push_back(r1);b.push_back(v1+1);S.erase(r1);}else if(v0%2==0&&r0!=n+1){F.add(p0,1);a.push_back(r0);b.push_back(v0+1);S.erase(r0);}else{cout<<"No"<<endl;return 0;}}//reverse(a.begin(),a.end());//reverse(b.begin(),b.end());cout<<"Yes"<<endl;rep(i,a.size()){cout<<a[i]<<' '<<b[i]<<endl;}return 0;}