結果
| 問題 | No.1051 PQ Permutation |
| ユーザー |
 ttttan2
|
| 提出日時 | 2020-05-08 23:24:42 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,594 bytes |
| コンパイル時間 | 2,734 ms |
| コンパイル使用メモリ | 177,040 KB |
| 実行使用メモリ | 16,528 KB |
| 最終ジャッジ日時 | 2023-09-19 08:11:02 |
| 合計ジャッジ時間 | 7,602 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,384 KB |
| testcase_01 | AC | 1 ms
4,384 KB |
| testcase_02 | AC | 1 ms
4,384 KB |
| testcase_03 | AC | 2 ms
4,380 KB |
| testcase_04 | WA | - |
| testcase_05 | AC | 1 ms
4,384 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,380 KB |
| testcase_08 | WA | - |
| testcase_09 | AC | 2 ms
4,380 KB |
| testcase_10 | WA | - |
| testcase_11 | AC | 1 ms
4,380 KB |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | AC | 1 ms
4,380 KB |
| testcase_15 | AC | 105 ms
16,344 KB |
| testcase_16 | AC | 118 ms
16,252 KB |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | AC | 161 ms
16,468 KB |
| testcase_22 | WA | - |
| testcase_23 | AC | 166 ms
16,192 KB |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | AC | 2 ms
4,380 KB |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | AC | 9 ms
4,384 KB |
| testcase_31 | WA | - |
| testcase_32 | AC | 8 ms
4,384 KB |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | AC | 49 ms
9,564 KB |
| testcase_37 | AC | 78 ms
14,692 KB |
| testcase_38 | AC | 101 ms
16,416 KB |
| testcase_39 | WA | - |
| testcase_40 | AC | 109 ms
14,512 KB |
| testcase_41 | AC | 107 ms
14,508 KB |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | AC | 1 ms
4,384 KB |
| testcase_45 | AC | 2 ms
4,380 KB |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:26:33: 警告: ‘n2’ may be used uninitialized [-Wmaybe-uninitialized]
26 | #define rep(i,m,n) for(int i=m;i<n;i++)
| ^
main.cpp:204:23: 備考: ‘n2’ はここで定義されています
204 | ll n1,n2;
| ^~
main.cpp:26:33: 警告: ‘n1’ may be used uninitialized [-Wmaybe-uninitialized]
26 | #define rep(i,m,n) for(int i=m;i<n;i++)
| ^
main.cpp:204:20: 備考: ‘n1’ はここで定義されています
204 | ll n1,n2;
| ^~
main.cpp:26:33: 警告: ‘n2’ may be used uninitialized [-Wmaybe-uninitialized]
26 | #define rep(i,m,n) for(int i=m;i<n;i++)
| ^
main.cpp:173:23: 備考: ‘n2’ はここで定義されています
173 | ll n1,n2;
| ^~
main.cpp:26:33: 警告: ‘n1’ may be used uninitialized [-Wmaybe-uninitialized]
26 | #define rep(i,m,n) for(int i=m;i<n;i++)
| ^
main.cpp:173:20: 備考: ‘n1’ はここで定義されています
173 | ll n1,n2;
| ^~
main.cpp:26:33: 警告: ‘n2’ may be used uninitialized [-Wmaybe-uninitialized]
26 | #define rep(i,m,n) for(int i=m;i<n;i++)
| ^
main.cpp:150:19: 備考: ‘n2’ はここで定義されています
150 | ll n1,n2;
| ^~
main.cpp:26:33: 警告: ‘n1’ may be used uninitialized [-Wmaybe-uninitialized]
26 | #define rep(i,m,n) for(int i=m;i<n;i++)
| ^
main.cpp:150:16: 備考: ‘n1’ はここで定義されています
150 | ll n1,n2;
| ^~
ソースコード
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef pair<pii,pii> P;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
typedef vector<vector<ll>> mat;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<62;
double pi=3.141592653589793238462643383279L;
double eps=1e-14;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto& itr:mp)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#define umh unordered_map<ll,ll,custom_hash>
ll gcd(ll a,ll b){
if(a<b)swap(a,b);
if(b==0)return a;
if(a%b==0)return b;
return gcd(b,a%b);
}
ll lcm(ll a,ll b){
ll c=gcd(a,b);
return a*b/c;
}
ll Pow(ll n,ll k){
ll ret=1;
ll now=n;
while(k>0){
if(k&1)ret*=now;
now*=now;
k/=2;
}
return ret;
}
ll beki(ll n,ll k,ll md){
ll ret=1;
ll now=n;
now%=md;
while(k>0){
if(k%2==1){
ret*=now;
ret%=md;
}
now*=now;
now%=md;
k/=2;
}
return ret;
}
ll gyaku(ll n,ll md){
return beki(n,md-2,md);
}
ll poc(ll n){
ll ret=0;
ll u=n;
while(u>0){
ret+=u%2;
u/=2;
}
return ret;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
ll n,p,q;cin>>n>>p>>q;
ll a[n];
rep(i,0,n)cin>>a[i];
bool bo[n];
fill(bo,bo+n,false);
bo[n-1]=true;
rrep(i,n-2,0){
if(a[i]>a[i+1])bo[i]=true;
else{
break;
}
}
vector<ll> ans;
set<ll> st;
rep(i,1,n+1)st.insert(i);
rep(i,0,n-1){
if(bo[i+1]){
ll now=a[i]+1;
if(now==n+1){
cout<<-1<<endl;
return 0;
}
if(now==p){
ans.push_back(now);
st.erase(now);
srep(itr,st)ans.push_back(*itr);
}
else if(now==q){
now++;
if(now==n+1){
cout<<-1<<endl;
return 0;
}
ans.push_back(now);
st.erase(now);
srep(itr,st)ans.push_back(*itr);
}
else{
ans.push_back(now);
st.erase(now);
srep(itr,st){
ans.push_back(*itr);
}
}
ll n1,n2;
rep(j,0,ans.size()){
if(ans[j]==p)n1=j;
else if(ans[j]==q)n2=j;
}
if(n1>n2){
rep(j,n2,n1)ans[j]=ans[j+1];
ans[n1]=q;
}
break;
}
else{
ll now=a[i];
if(now==q){
now++;
if(now==n+1){
cout<<-1<<endl;
return 0;
}
ans.push_back(now);
st.erase(now);
srep(itr,st)ans.push_back(*itr);
ll n1,n2;
rep(j,0,ans.size()){
if(ans[j]==p)n1=j;
else if(ans[j]==q)n2=j;
}
if(n1>n2){
rep(j,n2,n1)ans[j]=ans[j+1];
ans[n1]=q;
}
break;
}
else if(now==p){
ans.push_back(now);
st.erase(now);
rrep(j,i+1,n){
if(bo[j+1]){
ll ne=a[j]+1;
if(ne==n+1){
cout<<-1<<endl;
return 0;
}
ans.push_back(now);
st.erase(now);
srep(itr,st)ans.push_back(*itr);
break;
}
else{
ans.push_back(a[j]);
st.erase(a[j]);
}
}
ll n1,n2;
rep(j,0,ans.size()){
if(ans[j]==p)n1=j;
else if(ans[j]==q)n2=j;
}
if(n1>n2){
rep(j,n2,n1)ans[j]=ans[j+1];
ans[n1]=q;
}
break;
}
else{
ans.push_back(a[i]);
st.erase(a[i]);
}
}
}
rep(i,0,ans.size())cout<<ans[i]<<" ";
cout<<endl;
}