QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379801 | #2337. Azulejos | distant_yesterday# | AC ✓ | 399ms | 73632kb | C++20 | 4.2kb | 2024-04-06 19:11:34 | 2024-04-06 19:11:35 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
template<typename T> void write(T x) {
if(x > 9) write(x/10);
putchar(x%10 + '0');
}
vector<vector<pii>> get_groups(vector<tuple<int,int,int>> a) {
int last_price = -1;
vector<pii> last_group;
vector<vector<pii>> ans;
debug(a);
for(auto [price, height, idx]: a){
if(price != last_price) {
if(sz(last_group) > 0) {
ans.emplace_back(last_group);
last_group.clear();
}
last_price = price;
}
last_group.emplace_back(height, idx);
}
if(sz(last_group) > 0) {
ans.emplace_back(last_group);
}
return ans;
}
const int INF = 0x3f3f3f3f;
void solve() {
int n;
read(n);
vector<tuple<int,int,int>> front(n), back(n);
rep(i,0,n) read(get<0>(back[i]));
rep(i,0,n) read(get<1>(back[i]));
rep(i,0,n) read(get<0>(front[i]));
rep(i,0,n) read(get<1>(front[i]));
rep(i,0,n) {
get<2>(back[i])=i;
get<2>(front[i])=i;
}
sort(all(front));
sort(all(back));
vector<vector<pii>> back_groups = get_groups(back);
vector<vector<pii>> front_groups = get_groups(front);
debug(back_groups);
debug(front_groups);
vi ans_front(n, -1), ans_back(n, -1);
set<pii> cfront, cback;
int completed = 0, fg_id = 0, bg_id = 0;
while(completed < n) {
if(cfront.empty()) {
assert(fg_id < sz(front_groups));
for(auto p: front_groups[fg_id]) {
cfront.insert(p);
}
fg_id++;
}
if(cback.empty()) {
assert(bg_id < sz(back_groups));
for(auto p: back_groups[bg_id]) {
cback.insert(p);
}
bg_id++;
}
debug(cfront, cback);
if(sz(cfront) <= sz(cback)) {
while(cfront.size()) {
debug("1",completed,cfront, cback);
auto [val, pos] = *cfront.begin();
cfront.erase(cfront.begin());
auto it = cback.upper_bound({val, INF});
if(it == cback.end()) {
debug(val,pos,"GG");
cout<<"impossible"<<'\n';
return;
} else {
debug(val,pos,"matched", it->first,it->second);
ans_front[completed] = pos;
ans_back[completed] = it->second;
assert(it->first > val);
cback.erase(it);
completed++;
}
}
} else {
while(cback.size()) {
debug("2",completed,cfront, cback);
auto [val, pos] = *cback.begin();
cback.erase(cback.begin());
auto it = cfront.lower_bound({val, -INF});
if(it == cfront.begin()) {
debug(val,pos,"cannot go before begin");
cout<<"impossible"<<'\n';
return;
}
--it;
debug(val,pos,"matcheD", it->first,it->second);
ans_front[completed] = it->second;
ans_back[completed] = pos;
assert(val > it->first);
cfront.erase(it);
completed++;
}
}
}
rep(i,0,n) cout<<(ans_back[i]+1)<<" \n"[i==n-1];
rep(i,0,n) cout<<(ans_front[i]+1)<<" \n"[i==n-1];
}
signed main() {
int T; T = 1;
while(T--) solve();
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3576kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3524kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3600kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 3572kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 3532kb
Test #10:
score: 0
Accepted
time: 1ms
memory: 3568kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #12:
score: 0
Accepted
time: 241ms
memory: 73632kb
Test #13:
score: 0
Accepted
time: 1ms
memory: 3588kb
Test #14:
score: 0
Accepted
time: 1ms
memory: 3720kb
Test #15:
score: 0
Accepted
time: 4ms
memory: 4988kb
Test #16:
score: 0
Accepted
time: 1ms
memory: 3576kb
Test #17:
score: 0
Accepted
time: 1ms
memory: 3584kb
Test #18:
score: 0
Accepted
time: 0ms
memory: 3612kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 3636kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 3608kb
Test #21:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #22:
score: 0
Accepted
time: 48ms
memory: 8180kb
Test #23:
score: 0
Accepted
time: 35ms
memory: 11296kb
Test #24:
score: 0
Accepted
time: 54ms
memory: 11188kb
Test #25:
score: 0
Accepted
time: 42ms
memory: 10336kb
Test #26:
score: 0
Accepted
time: 184ms
memory: 73272kb
Test #27:
score: 0
Accepted
time: 37ms
memory: 17044kb
Test #28:
score: 0
Accepted
time: 43ms
memory: 17020kb
Test #29:
score: 0
Accepted
time: 46ms
memory: 17252kb
Test #30:
score: 0
Accepted
time: 30ms
memory: 17164kb
Test #31:
score: 0
Accepted
time: 399ms
memory: 73376kb
Test #32:
score: 0
Accepted
time: 57ms
memory: 17356kb
Test #33:
score: 0
Accepted
time: 303ms
memory: 73280kb