QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60014 | #2337. Azulejos | captured# | WA | 3ms | 5760kb | C++17 | 2.8kb | 2022-11-02 17:20:30 | 2022-11-02 17:20:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
struct D {
int p, h, idx;
} bck[maxn], frnt[maxn];
bool cmp(const D &a, const D &b) {
if (a.p == b.p) {
return a.h < b.h;
}
return a.p < b.p;
}
bool operator > (const pair<int, D> a, const pair<int, D> b) {
return a.first > b.first;
}
void solve(int cs){
int n, x;
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>x;
bck[i].p = x;
}
for (int i = 1; i <= n; i++) {
cin>>x;
bck[i].h = x;
bck[i].idx = i;
}
for (int i = 1; i <= n; i++) {
cin>>x;
frnt[i].p = x;
}
for (int i = 1; i <= n; i++) {
cin>>x;
frnt[i].h = x;
frnt[i].idx = i;
}
sort(frnt+1, frnt+n+1, cmp);
sort(bck+1, bck+n+1, cmp);
int f = 0, j = 1;
stack<D> q;
priority_queue<pair<int, int>> pq;
q.push(bck[1]);
vector<int> ans, ans2;
for (int i = 2; i<= n; i++) {
if (bck[i].p==bck[i-1].p) {
q.push(bck[i]);
}
else {
while (j < i) {
pq.push({frnt[j].h, frnt[j].idx});
j++;
}
while (j <= n && frnt[j].h < q.top().h && frnt[j].p == frnt[j-1].p) {
pq.push({frnt[j].h, frnt[j].idx});
j++;
}
while (q.empty()==0) {
// cout<<pq.top().first<<" "<<q.top().h<<endl;
if (pq.top().first < q.top().h) {
ans.push_back(q.top().idx);
ans2.push_back(pq.top().second);
}
else {
f = 1;
}
pq.pop();
q.pop();
}
q.push(bck[i]);
}
}
while (j <= n) {
pq.push({frnt[j].h, frnt[j].idx});
j++;
}
while (j <= n && frnt[j].h < q.top().h && frnt[j].p == frnt[j-1].p) {
pq.push({frnt[j].h, frnt[j].idx});
j++;
}
while (q.empty()==0) {
// cout<<pq.top().first<<" "<<q.top().h<<endl;
if (pq.top().first < q.top().h) {
ans.push_back(q.top().idx);
ans2.push_back(pq.top().second);
}
else {
f = 1;
}
pq.pop();
q.pop();
}
if (f == 1) {
cout<<"impossible\n";
return;
}
for (int i = 1; i<=n; i++) {
cout<<ans[i-1]<<" ";
}
cout<<"\n";
for (int i = 1; i<=n; i++) {
cout<<ans2[i-1]<<" ";
}
cout<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;t=1;
//cin>>t;
for(int cs=1;cs<=t;cs++)solve(cs);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 5596kb
Test #2:
score: 0
Accepted
time: 2ms
memory: 5588kb
Test #3:
score: 0
Accepted
time: 3ms
memory: 5760kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 5688kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 5688kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 5624kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 5696kb
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 5588kb