QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#60109 | #2337. Azulejos | captured | WA | 4ms | 7820kb | C++17 | 3.8kb | 2022-11-02 21:14:29 | 2022-11-02 21:14:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
const int maxn = 5e5+5;
struct D {
int p, h, idx;
} bck[maxn], frnt[maxn], X[maxn], Y[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 cmp2 (const pair<int, pair<int, int>> a, const pair<int, pair<int, int>> b) {
if (X[a.second.first].p == X[b.second.first].p) {
return Y[a.second.second].p < Y[b.second.second].p;
}
return X[a.second.first].p < X[b.second.first].p;
}
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;
// map<int, multiset<pair<int, int>>> mp, mp2;
//
// for (int i = 1; i <= n; i++) {
// mp[bck[i].p].insert({bck[i].h, bck[i].idx});
// }
// for (int i = 1; i <= n; i++) {
// mp2[frnt[i].p].insert({frnt[i].h, frnt[i].idx});
// }
// auto bc = mp.begin(), fr = mp2.begin();
// vector<pair<int, int>> ans;
// while (bc != mp.end() && fr != mp2.end()) {
// vector<pair<int, int> > tmp;
// for (auto x: fr.first) {
// if (bc.first.upper_bound(x.first) != bc.first.end()) {
// bc.first.erase()
// }
// }
// }
queue<pair<int, int > >st;
int pointerr = 1;
int pointerr2 = 1;
multiset <pair <int, int> >mp;
vector<int> ans1 ,ans2;
for(int i = 1; i <= n; i++)
{
if(st.empty())
{
int j = pointerr;
while(j <= n)
{
if(bck[j].p == bck[pointerr].p)
{
st.push({bck[j].h , bck[j].idx});
j++;
}
else
break;
}
pointerr = j;
}
if(mp.empty())
{
int j = pointerr2;
while(j <= n)
{
if(frnt[j].p == frnt[pointerr2].p)
{
mp.insert({frnt[j].h , frnt[j].idx});
j++;
}
else
break;
}
pointerr2 = j;
}
pair <int, int> tmp_f = st.front();
st.pop();
int val = tmp_f.first;
auto it = mp.lower_bound({val, 0});
// for(auto mp_x : mp)
// {
// cout << mp_x.first << " -> " << mp_x.second << endl;
// }
// cout << " for " << i << endl;
// cout << "searhinf " << val << " " <<(*it).first<<endl;
if(it == mp.begin())
{
f = 1;
break;
}
it--;
// cout << "searhinf " << val << " " <<(*it).first<<endl;
if((*it).first >= val)
assert(0);
ans1.push_back(tmp_f.second);
ans2.push_back((*it).second);
mp.erase(it);
}
if(f)
{
cout << "impossible" << endl;
}
else
{
for(auto x : ans1)
{
cout << x << " ";
}
cout << endl;
for(auto x : ans2)
{
cout << x << " ";
}
cout << endl;
}
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 7732kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 7632kb
Test #3:
score: 0
Accepted
time: 3ms
memory: 7716kb
Test #4:
score: 0
Accepted
time: 3ms
memory: 7716kb
Test #5:
score: 0
Accepted
time: 3ms
memory: 7820kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 7716kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 7816kb
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 7660kb