QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515983#2337. AzulejosYanagi_OrigamiAC ✓863ms50556kbC++141.7kb2024-08-12 12:38:222024-08-12 12:38:22

Judging History

This is the latest submission verdict.

  • [2024-08-12 12:38:22]
  • Judged
  • Verdict: AC
  • Time: 863ms
  • Memory: 50556kb
  • [2024-08-12 12:38:22]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N = 500005;
int n,ord1[N],ord2[N],cnt,ans[2][N],h1[N],h2[N],p1[N],p2[N];
std::set<tuple<int,int,int>> s1, s2;

int main() {
	cin>>n;
	rep(i,1,n) cin>>p1[i];
	rep(i,1,n) cin>>h1[i];
	rep(i,1,n) cin>>p2[i];
	rep(i,1,n) cin>>h2[i];
	rep(i,1,n) ord1[i]=ord2[i]=i;
	auto p=p1;

	auto cmp=[&p](int a,int b){ return p[a]<p[b]; };
	sort(ord1+1,ord1+n+1,cmp);
	p=p2;
	sort(ord2+1,ord2+n+1,cmp);
	//rep(i,1,n) cout<<ord1[i]<<' '; puts("");
	//rep(i,1,n) cout<<ord2[i]<<' '; puts("");
	rep(i,0,n){
		if(p1[ord1[i]]!=p1[ord1[i+1]]||p2[ord2[i]]!=p2[ord2[i+1]]){
			if(s1.size()<s2.size()){
				for(auto w:s1){
					auto it=s2.lower_bound(make_tuple(get<0>(w), 1, 0));
					if(it!=s2.begin()){
						cnt++, it--;
						ans[0][cnt]=get<1>(w);
						ans[1][cnt]=get<1>(*it);
						s2.erase(it);
					}else{
						puts("impossible");
						return 0;
					}
				}
				s1.clear();
			}else{
				for(auto w:s2){
					auto it=s1.upper_bound(make_tuple(get<0>(w), n, (int)1e9));
					if(it!=s1.end()){
						cnt++;
						ans[0][cnt]=get<1>(*it);
						ans[1][cnt]=get<1>(w);
						s1.erase(it);
					}else{
						puts("impossible");
						return 0;
					}
				}
				s2.clear();
			}
			if(p1[ord1[i]]!=p1[ord1[i+1]])
				rep(j,i+1,n)
					if(p1[ord1[j]]==p1[ord1[i+1]])
						s1.insert(make_tuple(h1[ord1[j]],ord1[j],p1[ord1[j]]));
					else
						break;
			if(p2[ord2[i]]!=p2[ord2[i+1]])
				rep(j,i+1,n)
					if(p2[ord2[j]]==p2[ord2[i+1]])
						s2.insert(make_tuple(h2[ord2[j]],ord2[j],p2[ord2[j]]));
					else
						break;
		}
	}

	rep(i,1,n) cout<<ans[0][i]<<' '; cout<<'\n';
	rep(i,1,n) cout<<ans[1][i]<<' ';
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 2ms
memory: 15980kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 13936kb

Test #3:

score: 0
Accepted
time: 2ms
memory: 17880kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 13852kb

Test #5:

score: 0
Accepted
time: 2ms
memory: 15836kb

Test #6:

score: 0
Accepted
time: 2ms
memory: 13932kb

Test #7:

score: 0
Accepted
time: 2ms
memory: 15892kb

Test #8:

score: 0
Accepted
time: 2ms
memory: 15960kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 17936kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 17960kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 17900kb

Test #12:

score: 0
Accepted
time: 455ms
memory: 50428kb

Test #13:

score: 0
Accepted
time: 3ms
memory: 18024kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 18088kb

Test #15:

score: 0
Accepted
time: 7ms
memory: 16496kb

Test #16:

score: 0
Accepted
time: 3ms
memory: 18020kb

Test #17:

score: 0
Accepted
time: 0ms
memory: 18032kb

Test #18:

score: 0
Accepted
time: 0ms
memory: 15856kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 17968kb

Test #20:

score: 0
Accepted
time: 2ms
memory: 17916kb

Test #21:

score: 0
Accepted
time: 0ms
memory: 15920kb

Test #22:

score: 0
Accepted
time: 89ms
memory: 18364kb

Test #23:

score: 0
Accepted
time: 112ms
memory: 21024kb

Test #24:

score: 0
Accepted
time: 136ms
memory: 21088kb

Test #25:

score: 0
Accepted
time: 58ms
memory: 18336kb

Test #26:

score: 0
Accepted
time: 425ms
memory: 50472kb

Test #27:

score: 0
Accepted
time: 86ms
memory: 24584kb

Test #28:

score: 0
Accepted
time: 108ms
memory: 24644kb

Test #29:

score: 0
Accepted
time: 88ms
memory: 24660kb

Test #30:

score: 0
Accepted
time: 70ms
memory: 22772kb

Test #31:

score: 0
Accepted
time: 863ms
memory: 50492kb

Test #32:

score: 0
Accepted
time: 149ms
memory: 22624kb

Test #33:

score: 0
Accepted
time: 674ms
memory: 50556kb