QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515977#2337. AzulejosYanagi_OrigamiWA 3ms18012kbC++141.7kb2024-08-12 12:33:592024-08-12 12:34:00

Judging History

This is the latest submission verdict.

  • [2024-08-12 12:34:00]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 18012kb
  • [2024-08-12 12:33:59]
  • 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, 0));
					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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 17940kb

Test #2:

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

Test #3:

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

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 18012kb