QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515983 | #2337. Azulejos | Yanagi_Origami | AC ✓ | 863ms | 50556kb | C++14 | 1.7kb | 2024-08-12 12:38:22 | 2024-08-12 12:38:22 |
Judging History
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;
}
詳細信息
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