QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#875184 | #9641. Two permutations | ucup-team052 | 0 | 281ms | 13256kb | C++23 | 1.6kb | 2025-01-29 12:17:49 | 2025-01-29 12:17:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 400005
int pre[N],suf[N],v[N],a[N],pos[N],op[N],n;
void work()
{
cin>>n;
for(int i=1;i<=n;i++)
{
v[i]=read();
if(v[i]>i)
{
cout<<"No\n";
return ;
}
}
memset(pre,0,sizeof(pre));
memset(suf,0,sizeof(suf));
int H=0,T=2*n+1;
suf[H]=T,pre[T]=H;
auto ins=[&](int pos,int val) // pos (val) pos+1
{
int nxt=suf[pos];
suf[pos]=val,pre[val]=pos;
suf[val]=nxt,pre[nxt]=val;
};
int mid=H;
for(int i=1;i<=n;i++)
{
if(v[i]==i)
{
ins(mid,i);
ins(H,i+n);
pos[i]=i+n;
op[i]=1,op[i+n]=0;
if(i==1) mid=i+n;
}
else
{
int p=pos[v[i]],o=op[p];
if(o==0)
{
ins(pre[T],i),op[i]=1,pos[i]=i;
ins(pre[p],i+n),op[i+n]=0;
}
else
{
ins(H,i),op[i]=0,pos[i]=i;
ins(p,i+n),op[i+n]=1;
}
}
}
int cur=H;
for(int i=1;i<=2*n;i++)
{
cur=suf[cur];
if(cur<=n) a[i]=cur;
else a[i]=cur-n;
}
for(int i=1;i<=n*2;i++) printf("%d%c",a[i]," \n"[i==n*2]);
}
signed main()
{
int T=read(); while(T--) work();
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11904kb
input:
10 1 1 2 1 1 3 1 2 2 4 1 1 3 2 5 1 2 1 2 1 2 1 1 1 1 3 1 2 2 1 1 5 1 1 1 3 2
output:
1 1 2 1 1 2 3 2 1 2 1 3 4 3 2 1 3 1 2 4 4 2 3 5 1 2 1 3 4 5 2 1 1 2 1 1 3 2 1 2 1 3 1 1 5 4 2 3 1 1 2 5 3 4
result:
wrong answer Wrong Answer![1]
Subtask #2:
score: 0
Wrong Answer
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 11992kb
input:
10 10 1 2 3 4 3 1 2 4 3 8 10 1 2 1 1 4 6 4 5 2 9 10 1 2 2 4 5 3 7 7 2 3 10 1 1 2 4 5 4 3 5 7 7 10 1 2 2 4 4 1 6 6 6 10 10 1 2 2 4 1 3 7 7 1 10 10 1 2 3 4 2 1 3 3 1 7 10 1 1 1 4 5 1 3 5 4 7 10 1 2 2 1 1 2 6 5 8 5 10 1 2 2 2 5 3 6 2 4 5
output:
10 8 4 5 9 3 7 2 6 1 4 3 2 1 5 6 7 8 10 9 10 7 6 8 5 9 2 3 4 1 6 2 1 3 4 7 5 8 9 10 10 8 7 6 5 4 3 9 2 1 7 5 4 2 1 3 10 6 8 9 10 9 8 5 6 4 7 3 2 1 5 4 1 2 3 6 7 10 9 8 10 9 8 7 5 4 3 2 6 1 10 4 2 1 3 5 6 9 8 7 10 8 7 6 4 3 2 5 9 1 10 7 4 2 1 3 6 5 8 9 10 4 7 8 3 5 2 6 9 1 4 3 2 1 5 6 7 10 8 9 10 7 8...
result:
wrong answer Wrong Answer![1]
Subtask #3:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 86ms
memory: 13092kb
input:
10 177329 1 1 2 2 1 4 1 2 3 3 2 3 4 1 2 3 3 2 2 2 2 3 4 3 1 2 4 2 4 1 4 2 2 4 1 3 3 4 1 1 1 3 2 4 3 3 2 4 2 2 4 1 1 4 3 1 4 4 4 3 1 4 1 3 2 1 2 3 2 4 2 4 4 2 1 3 2 2 2 3 3 1 4 1 3 1 2 4 1 4 2 3 4 3 1 4 4 1 2 2 3 3 4 1 4 4 3 4 3 2 1 2 4 3 1 1 4 4 4 2 3 4 3 3 3 1 4 4 1 1 2 4 4 1 3 4 4 4 2 1 2 2 1 2 3 ...
output:
177328 177326 177324 177321 177317 177313 177312 177311 177308 177294 177292 177290 177278 177270 177265 177262 177253 177242 177237 177233 177232 177213 177212 177210 177206 177191 177189 177188 177187 177180 177179 177175 177172 177168 177165 177164 177162 177155 177151 177145 177143 177140 177125...
result:
wrong answer Wrong Answer![1]
Subtask #4:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 244ms
memory: 13256kb
input:
10 199850 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
199850 199849 199848 199847 199846 199845 199844 199843 199842 199841 199840 199839 199838 199837 199836 199835 199834 199833 199832 199831 199830 199829 199828 199827 199826 199825 199824 199823 199822 199821 199820 199819 199818 199817 199816 199815 199814 199813 199812 199811 199810 199809 199808...
result:
wrong answer Wrong Answer![1]
Subtask #5:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 281ms
memory: 13148kb
input:
10 199755 1 2 1 3 5 1 6 7 2 1 5 6 10 9 12 2 4 14 2 18 5 17 23 4 6 7 4 6 20 27 16 24 29 8 33 26 33 27 17 39 5 33 34 41 4 16 24 19 42 8 29 48 48 27 37 24 43 13 4 28 38 27 38 23 29 55 14 62 26 9 62 20 35 31 57 74 69 5 26 60 33 59 5 19 21 45 15 87 3 54 17 2 57 36 18 67 25 62 47 53 89 27 5 59 75 77 29 9 ...
output:
199755 199754 199748 199743 199741 199739 199738 199737 199735 199734 199732 199729 199728 199726 199722 199718 199714 199713 199712 199710 199709 199708 199706 199705 199704 199703 199700 199695 199694 199692 199691 199688 199687 199685 199683 199682 199681 199680 199679 199678 199677 199676 199674...
result:
wrong answer Wrong Answer![1]