結果
問題 | No.1051 PQ Permutation |
ユーザー | mugen_1337 |
提出日時 | 2020-05-09 10:44:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,745 bytes |
コンパイル時間 | 2,499 ms |
コンパイル使用メモリ | 209,256 KB |
実行使用メモリ | 14,244 KB |
最終ジャッジ日時 | 2023-09-19 08:18:12 |
合計ジャッジ時間 | 7,195 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | WA | - |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 96 ms
14,124 KB |
testcase_16 | AC | 108 ms
13,792 KB |
testcase_17 | AC | 37 ms
4,376 KB |
testcase_18 | AC | 36 ms
4,380 KB |
testcase_19 | AC | 36 ms
4,376 KB |
testcase_20 | AC | 151 ms
13,780 KB |
testcase_21 | AC | 144 ms
14,112 KB |
testcase_22 | AC | 36 ms
4,380 KB |
testcase_23 | AC | 150 ms
13,800 KB |
testcase_24 | AC | 154 ms
13,832 KB |
testcase_25 | AC | 9 ms
4,376 KB |
testcase_26 | AC | 3 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 6 ms
4,380 KB |
testcase_29 | AC | 3 ms
4,376 KB |
testcase_30 | AC | 9 ms
4,384 KB |
testcase_31 | AC | 4 ms
4,380 KB |
testcase_32 | AC | 7 ms
4,380 KB |
testcase_33 | AC | 2 ms
4,380 KB |
testcase_34 | AC | 2 ms
4,376 KB |
testcase_35 | WA | - |
testcase_36 | AC | 44 ms
8,568 KB |
testcase_37 | AC | 19 ms
4,380 KB |
testcase_38 | AC | 92 ms
13,840 KB |
testcase_39 | AC | 143 ms
13,792 KB |
testcase_40 | AC | 34 ms
4,376 KB |
testcase_41 | AC | 101 ms
14,244 KB |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | AC | 2 ms
4,376 KB |
testcase_45 | AC | 1 ms
4,380 KB |
testcase_46 | AC | 2 ms
4,376 KB |
testcase_47 | AC | 1 ms
4,376 KB |
testcase_48 | AC | 156 ms
13,908 KB |
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内: main.cpp:4:31: 警告: ‘qi’ may be used uninitialized [-Wmaybe-uninitialized] 4 | #define rep(i,n) for(int i=0;i<(n);i++) | ^ main.cpp:30:12: 備考: ‘qi’ はここで定義されています 30 | int pi,qi; | ^~ main.cpp:36:5: 警告: ‘pi’ may be used uninitialized [-Wmaybe-uninitialized] 36 | if(pi<qi){ | ^~ main.cpp:30:9: 備考: ‘pi’ はここで定義されています 30 | int pi,qi; | ^~
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define INF 1000000000 #define mod 1000000007 using ll=long long; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,p,q;cin>>n>>p>>q;p--,q--; vector<int> a(n); rep(i,n){ cin>>a[i];a[i]--; } if(!next_permutation(ALL(a))){ cout<<-1<<endl; return 0; } int pi,qi; rep(i,n){ if(a[i]==p) pi=i; if(a[i]==q) qi=i; } if(pi<qi){ rep(i,n) cout<<a[i]+1<<(i+1==n?"\n":" "); return 0; } vector<int> ans(n); bool f=true;//答え作れますフラグ // qより前すべて一致 { set<int> st;rep(i,n)st.insert(i); rep(i,qi){ ans[i]=a[i]; st.erase(ans[i]); } auto ite=st.lower_bound(q+1); if(ite==st.end()) f=false; if(f) st.erase(ite); ans[qi]=*ite; bool pPlaced=false; if(ans[qi]==p) pPlaced=true; for(int i=qi+1;i<n and f;i++){ auto ite=st.begin(); if(*ite==q and !pPlaced){ ite=next(ite); if(ite==st.end()){ f=false; break; } ans[i]=*ite; st.erase(ite); }else{ ans[i]=*ite; st.erase(ite); } if(ans[i]==p) pPlaced=true; } } // qより前の順列を1個進め,それ以降貪欲にp->qだけ満たすように配置 if(!f){ set<int> st;rep(i,n)st.insert(i); rep(i,qi){ ans[i]=a[i]; st.erase(ans[i]); } if(!next_permutation(ans.begin(),ans.begin()+qi)){ cout<<-1<<endl; return 0; } bool pPlaced=false; for(int i=qi;i<n;i++){ auto ite=st.begin(); if(*ite==q and !pPlaced){ ite=next(ite); if(ite==st.end()){ cout<<-1<<endl; return 0; } ans[i]=*ite; st.erase(ite); }else{ ans[i]=*ite; } if(ans[i]==p)pPlaced=true; } } rep(i,n) cout<<ans[i]+1<<(i+1==n?"\n":" "); return 0; }