QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94709#2337. AzulejosDaiRuiChen007AC ✓1344ms110716kbC++141.4kb2023-04-07 15:55:402023-04-07 15:55:40

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 15:55:40]
  • Judged
  • Verdict: AC
  • Time: 1344ms
  • Memory: 110716kb
  • [2023-04-07 15:55:40]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
struct node {
	int q,h,id;
	inline friend bool operator <(const node &A,const node &B) {
		if(A.h==B.h) return A.id<B.id;
		return A.h<B.h;
	}
	node(int _q=0,int _h=0,int _id=0): q(_q),h(_h),id(_id) {}
}	a[MAXN],b[MAXN];
int s[MAXN],t[MAXN];
set <node> A,B;
map <int,vector<node>> C,D;
signed main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i].q),a[i].id=i;
	for(int i=1;i<=n;++i) scanf("%d",&a[i].h),C[a[i].q].push_back(a[i]);
	for(int i=1;i<=n;++i) scanf("%d",&b[i].q),b[i].id=i;
	for(int i=1;i<=n;++i) scanf("%d",&b[i].h),D[b[i].q].push_back(b[i]);
	auto it1=C.begin(),it2=D.begin();
	for(int i=1;i<=n;++i) {
		if(A.empty()) {
			for(auto x:it1->second) A.insert(x);
			++it1;
		}
		if(B.empty()) {
			for(auto x:it2->second) B.insert(x);
			++it2;
		}
		if(A.size()<B.size()) {
			auto x=A.begin();
			auto y=B.upper_bound(node(0,x->h-1,n+1));
			if(y==B.begin()) { puts("impossible"); return 0; }
			--y;
			s[i]=x->id,t[i]=y->id;
			A.erase(x),B.erase(y);
		} else {
			auto y=B.begin();
			auto x=A.lower_bound(node(0,y->h+1,0));
			if(x==A.end()) { puts("impossible"); return 0; }
			s[i]=x->id,t[i]=y->id;
			A.erase(x),B.erase(y);
		}
	}
	for(int i=1;i<=n;++i) printf("%d ",s[i]); puts("");
	for(int i=1;i<=n;++i) printf("%d ",t[i]); puts("");
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 0ms
memory: 17228kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 16536kb

Test #3:

score: 0
Accepted
time: 6ms
memory: 18072kb

Test #4:

score: 0
Accepted
time: 6ms
memory: 16984kb

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

score: 0
Accepted
time: 1ms
memory: 17472kb

Test #9:

score: 0
Accepted
time: 6ms
memory: 18648kb

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 565ms
memory: 110716kb

Test #13:

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

Test #14:

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

Test #15:

score: 0
Accepted
time: 14ms
memory: 19944kb

Test #16:

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

Test #17:

score: 0
Accepted
time: 1ms
memory: 17260kb

Test #18:

score: 0
Accepted
time: 1ms
memory: 18716kb

Test #19:

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

Test #20:

score: 0
Accepted
time: 1ms
memory: 17420kb

Test #21:

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

Test #22:

score: 0
Accepted
time: 80ms
memory: 21548kb

Test #23:

score: 0
Accepted
time: 81ms
memory: 24784kb

Test #24:

score: 0
Accepted
time: 109ms
memory: 25792kb

Test #25:

score: 0
Accepted
time: 83ms
memory: 25056kb

Test #26:

score: 0
Accepted
time: 508ms
memory: 110516kb

Test #27:

score: 0
Accepted
time: 102ms
memory: 36804kb

Test #28:

score: 0
Accepted
time: 153ms
memory: 36024kb

Test #29:

score: 0
Accepted
time: 118ms
memory: 36984kb

Test #30:

score: 0
Accepted
time: 83ms
memory: 35900kb

Test #31:

score: 0
Accepted
time: 1344ms
memory: 110468kb

Test #32:

score: 0
Accepted
time: 173ms
memory: 36968kb

Test #33:

score: 0
Accepted
time: 1294ms
memory: 110564kb