oj.uz

Submission #1055781

# Submission time Handle Problem Language Result Execution time Memory
1055781 2024-08-13T05:19:00 Z d(#11110) Pizza Party (CCO24_day1problem2) C++17
12 / 12
 574 ms 95568 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
using tii=array<int,3>;
const int N=1000005;
int n,mx,a[N],b[N],cnt[N],k,ans[N];
tii v[N];
set<pii,greater<pii>> S;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
		v[a[i]][0]=i;
		mx=max(mx,a[i]);
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		cnt[b[i]]--;
		if(cnt[b[i]]<0){
			cout<<"-1\n";
			return 0;
		}
		v[b[i]][1]=n+1-i;
	}
	if(mx<=2){
		bool ok=true;
		for(int i=1;i<=n;i++) ok&=b[i]==a[n+1-i];
		if(ok){
			cout<<"1\n";
			for(int i=1;i<=n;i++) cout<<1<<" \n"[i==n];
			for(int i=1;i<=n;i++) cout<<1<<" \n"[i==n];
			return 0;
		}
		cout<<"2\n";
		for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];
		for(int i=1;i<=n;i++) cout<<b[i]<<" \n"[i==n];
		return 0;
	}
	for(int i=1;i<=n;i++) v[i][2]=i;
	sort(v+1,v+n+1);
	for(int i=1;i<=n;i++){
		int val=v[i][1];
		auto iter=S.lower_bound({val,-1});
		if(iter==S.end()){
			k++;
			S.insert({val,k});
			ans[v[i][2]]=k;
			continue;
		}
		int g=(*iter)[1];
		S.erase(iter);
		S.insert({val,g});
		ans[v[i][2]]=g;
	}
	cout<<k<<"\n";
	for(int i=1;i<=n;i++) cout<<ans[a[i]]<<" \n"[i==n];
	for(int i=1;i<=n;i++) cout<<ans[b[i]]<<" \n"[i==n];
	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 12116 KB good job!
2 Correct 132 ms 14168 KB good job!
3 Correct 126 ms 14164 KB good job!
4 Correct 150 ms 14168 KB good job!
5 Correct 128 ms 14420 KB good job!
6 Correct 131 ms 14240 KB good job!
7 Correct 125 ms 14236 KB good job!
8 Correct 125 ms 12368 KB good job!
9 Correct 126 ms 12372 KB good job!
10 Correct 125 ms 12116 KB good job!
11 Correct 123 ms 12116 KB good job!
12 Correct 127 ms 12112 KB good job!
13 Correct 0 ms 344 KB good job!
14 Correct 0 ms 348 KB good job!
15 Correct 0 ms 344 KB good job!
16 Correct 61 ms 8064 KB good job!
17 Correct 53 ms 8276 KB good job!
18 Correct 54 ms 8224 KB good job!
19 Correct 55 ms 8276 KB good job!
20 Correct 54 ms 8204 KB good job!
21 Correct 62 ms 8272 KB good job!
22 Correct 123 ms 12112 KB good job!
23 Correct 0 ms 348 KB good job!

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB good job!
2 Correct 1 ms 348 KB good job!
3 Correct 2 ms 604 KB good job!
4 Correct 0 ms 348 KB good job!
5 Correct 2 ms 604 KB good job!
6 Correct 0 ms 348 KB good job!
7 Correct 0 ms 348 KB good job!
8 Correct 2 ms 604 KB good job!
9 Correct 2 ms 604 KB good job!
10 Correct 2 ms 600 KB good job!
11 Correct 2 ms 860 KB good job!
12 Correct 1 ms 604 KB good job!
13 Correct 2 ms 856 KB good job!
14 Correct 1 ms 604 KB good job!
15 Correct 0 ms 348 KB good job!

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 36828 KB good job!
2 Correct 80 ms 20304 KB good job!
3 Correct 445 ms 39456 KB good job!
4 Correct 101 ms 22868 KB good job!
5 Correct 438 ms 37456 KB good job!
6 Correct 94 ms 23864 KB good job!
7 Correct 105 ms 23120 KB good job!
8 Correct 448 ms 36692 KB good job!
9 Correct 459 ms 43556 KB good job!
10 Correct 452 ms 43600 KB good job!
11 Correct 574 ms 95568 KB good job!
12 Correct 324 ms 32084 KB good job!
13 Correct 568 ms 88660 KB good job!
14 Correct 328 ms 32080 KB good job!
15 Correct 113 ms 22552 KB good job!
16 Correct 115 ms 22848 KB good job!