QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#515667	#4800. Oscar's Round Must Have a Constructive Problem	huaxiamengjin	AC ✓	106ms	5952kb	C++14	848b	2024-08-11 20:22:08	2024-08-11 20:22:08

Judging History

你现在查看的是最新测评结果

[2024-08-11 20:22:08]
评测

测评结果：AC
用时：106ms
内存：5952kb

查看

[2024-08-11 20:22:08]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int  n;
int a[100100],used[100100],uk[100100];
void solve(){
	cin>>n;
	vector<int>vv,v,ans;
	for (int i=1;i<=n;i++)uk[i]=0;
	for (int i=1;i<=n;i++)
	cin>>a[i],v.push_back(a[i]),used[i]=0,uk[a[i]]=1;
	for (int i=1;i<=n;i++)
	if(uk[i]==0)vv.push_back(i);
	for (int i=1;i<=n;i++){
		int fl=0;
		while(v.size()&&(used[v.back()]==1||v.back()==a[i]))v.pop_back(),fl=1;
		if(v.size())ans.push_back(v.back()),used[v.back()]=1,v.pop_back();
		else {
			int fll=0;
			while(vv.size()&&vv.back()==a[i])vv.pop_back(),fll=1;
			if(vv.size())ans.push_back(vv.back()),vv.pop_back();
			else return puts("NO"),void();
			if(fll)vv.push_back(a[i]);
		}
		if(fl)v.push_back(a[i]);
	}
	puts("YES");
	for (auto i:ans)cout<<i<<" ";cout<<"\n";
}
int main(){
	int T;cin>>T;
	while(T--)solve();
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3528kb

input:

3
3
3 3 3
3
3 2 1
6
1 1 4 5 1 4

output:

NO
YES
1 3 2 
YES
4 5 1 6 3 2

result:

ok ok

Test #2:

score: 0

Accepted

time: 86ms

memory: 3824kb

input:

output:

NO
NO
YES
2 1 
YES
1 2 
NO
NO
YES
2 3 1 
YES
3 2 1 
YES
2 1 3 
YES
2 1 3 
YES
3 1 2 
YES
3 1 2 
YES
2 1 3 
YES
3 1 2 
YES
1 2 3 
YES
1 2 3 
YES
3 2 1 
YES
1 3 2 
NO
YES
3 1 2 
YES
1 2 3 
YES
3 2 1 
YES
3 2 1 
YES
1 3 2 
YES
2 3 1 
YES
1 3 2 
YES
1 3 2 
YES
2 3 1 
YES
2 3 1 
YES
1 2 3 
YES
2 1 3 
NO
...

result:

ok ok

Test #3:

score: 0

Accepted

time: 40ms

memory: 3744kb

input:

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok ok

Test #4:

score: 0

Accepted

time: 106ms

memory: 3604kb

input:

50000
10
3 3 3 3 3 6 3 3 3 3
10
4 5 5 5 5 5 5 5 5 5
10
8 8 8 8 8 8 8 1 8 8
10
6 6 6 6 6 6 6 6 6 2
10
4 4 4 5 4 4 4 4 4 4
10
4 5 4 4 4 10 10 4 5 10
10
8 10 10 6 4 8 4 7 10 4
10
8 8 8 8 8 8 8 8 8 8
10
4 4 4 9 10 10 10 10 4 1
10
4 4 4 4 4 1 4 4 4 4
10
5 5 5 5 6 6 5 6 5 6
10
10 10 10 10 10 10 10 10 10 1...

output:

YES
6 10 9 8 7 3 5 4 2 1 
YES
5 4 10 9 8 7 6 3 2 1 
YES
1 10 9 7 6 5 4 8 3 2 
YES
2 10 9 8 7 5 4 3 1 6 
YES
5 10 9 4 8 7 6 3 2 1 
YES
10 4 5 9 8 7 6 3 2 1 
YES
4 7 8 10 6 9 5 3 2 1 
NO
YES
1 10 9 4 8 7 6 5 3 2 
YES
1 10 9 8 7 4 6 5 3 2 
YES
6 10 9 8 5 7 4 3 2 1 
NO
NO
YES
3 6 10 9 8 7 5 4 2 1 
YES
3...

result:

ok ok

Test #5:

score: 0

Accepted

time: 76ms

memory: 3592kb

input:

5000
100
37 37 37 58 58 58 58 58 58 58 37 58 37 37 37 58 37 37 37 37 58 58 37 37 37 37 58 37 58 58 58 58 37 58 58 58 37 58 37 37 37 37 58 37 37 37 58 37 37 58 37 37 37 58 37 37 58 37 58 58 58 58 37 37 58 58 58 37 37 58 58 37 37 58 37 58 58 37 58 58 58 37 58 58 37 58 58 58 37 58 58 58 37 58 58 37 58 ...

output:

YES
58 100 99 37 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
YES...

result:

ok ok

Test #6:

score: 0

Accepted

time: 78ms

memory: 3628kb

input:

500
1000
452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452...

output:

NO
NO
NO
YES
657 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 93...

result:

ok ok

Test #7:

score: 0

Accepted

time: 90ms

memory: 3992kb

input:

50
10000
9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9...

output:

YES
1755 10000 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945 9944 9943 ...

result:

ok ok

Test #8:

score: 0

Accepted

time: 93ms

memory: 4200kb

input:

20
25000
2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2...

output:

YES
15657 25000 24999 24998 24997 24996 24995 24994 24993 24992 24991 24990 24989 24988 24987 24986 24985 24984 24983 24982 24981 24980 24979 24978 24977 24976 24975 24974 24973 24972 24971 24970 24969 24968 24967 24966 24965 24964 24963 24962 24961 24960 24959 24958 24957 24956 24955 24954 24953 24...

result:

ok ok

Test #9:

score: 0

Accepted

time: 100ms

memory: 4608kb

input:

10
50000
32825 31708 22702 32825 22702 31708 32825 32825 9333 31708 32825 46864 22702 32825 31708 31708 22702 22702 31708 46864 9333 9333 1785 31708 22702 9333 1785 32825 31708 22702 46864 32825 9333 46864 9333 35050 31708 1785 46864 9333 32825 1785 22702 31708 22702 1785 46864 32825 1785 35050 9333...

output:

YES
46864 32825 35050 22702 1785 9333 31708 8079 50000 49999 49998 49997 49996 49995 49994 49993 49992 49991 49990 49989 49988 49987 49986 49985 49984 49983 49982 49981 49980 49979 49978 49977 49976 49975 49974 49973 49972 49971 49970 49969 49968 49967 49966 49965 49964 49963 49962 49961 49960 49959...

result:

ok ok

Test #10:

score: 0

Accepted

time: 93ms

memory: 5952kb

input:

5
100000
25575 25575 25575 25575 38740 38740 25575 38740 25575 38740 25575 25575 25575 38740 38740 38740 25575 38740 25575 25575 25575 25575 38740 38740 38740 38740 25575 25575 25575 38740 38740 25575 25575 38740 25575 38740 25575 38740 38740 25575 38740 38740 25575 38740 25575 25575 38740 38740 255...

output:

YES
38740 92905 100000 99999 25575 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 9...

result:

ok ok