icpc 2019 word final A問題の考え方

タイトルリンク

に言及

2列の品物の配置、各品物は価格と高さの2つの属性があります
要件:

each前列高さは後列

より小さい

行の価格は左から右へ

下落しない.

solution

まず各行を価格順に並べ替えます
各行は価格が同じものをbufferに入れます.buffer.size()の小さいそれを固定してそれから別のbufferで貪欲に同等の価格で取ることができる高さの中で最大です.buffer空き時間補充
「犯すことができる過ちは全部犯した」

#include 
using namespace std;
const int N = 5e5 + 7;

struct Node{
    int idx, price, height;

    Node (){}
    Node (int id, int p, int h):idx(id), price(p), height(h){}

    friend bool operator < (const Node &a,const Node &b){
        return a.height < b.height;
    }

    void print(){
        printf("Node %d: p = %d, h = %d
", idx, price, height);
    }
}fro[N], bac[N];

bool cmp (const Node &a,const Node &b){
    return a.price < b.price;
}

int n;
multiset  fro_buffer, bac_buffer;
multiset  :: iterator it;
vector  ans_fro, ans_bac;

void add_buffer(multiset  &buffer, Node* arr, int &idx){
    //printf("add_buffer:
");
    for (;idx <= n;){
        buffer.insert(arr[idx++]);
        //printf("\tadd(idx = %d) size = %d: ", idx-1, buffer.size()); arr[idx-1].print();
        if (arr[idx].price != arr[idx-1].price) return;
    }
}

bool fro_find_bac(){
    Node x = *fro_buffer.begin();
    ans_fro.push_back(x.idx);
    fro_buffer.erase(fro_buffer.begin());

    it = bac_buffer.upper_bound(x);
    if (it == bac_buffer.end()) return false;
    //printf("Back %d: p = %d, h = %d
", it->idx, it->price, it->height); x.print();
    
    ans_bac.push_back(it->idx);
    bac_buffer.erase(it);
    return true;
}

bool bac_find_fro(){
    Node x = *bac_buffer.begin();
    ans_bac.push_back(x.idx);
    bac_buffer.erase(bac_buffer.begin());

    it = fro_buffer.lower_bound(x);

    if (it == fro_buffer.begin()) return false;
    it = prev(it);
    //x.print(); printf("Front%d: p = %d, h = %d
", it->idx, it->price, it->height);

    ans_fro.push_back(it->idx);
    fro_buffer.erase(it);
    return true;
}

bool work(){
    fro_buffer.clear();
    bac_buffer.clear();
    int fro_idx = 1, bac_idx = 1;
    ans_fro.clear();
    ans_bac.clear();
    for (int i = 1; i <= n; i++){
        //printf("size: %d : %d
", bac_buffer.size(), fro_buffer.size());
        if (bac_buffer.empty()){
            add_buffer(bac_buffer, bac, bac_idx);
        }
        if (fro_buffer.empty()){
            add_buffer(fro_buffer, fro, fro_idx);
        }

        //printf("size: %d : %d
", bac_buffer.size(), fro_buffer.size());
        if (fro_buffer.size() < bac_buffer.size()){
            if (!fro_find_bac()) return false;
        }else{
            if (!bac_find_fro()) return false;
        }
    }
    return true;
}

int main(){
    //freopen("in.txt", "r", stdin);
    for (; ~scanf("%d", &n);){
        for (int i = 1; i <= n; i++) fro[i].idx = bac[i].idx = i;
        for (int i = 1; i <= n; i++) scanf("%d", &bac[i].price);
        for (int i = 1; i <= n; i++) scanf("%d", &bac[i].height);
        for (int i = 1; i <= n; i++) scanf("%d", &fro[i].price);
        for (int i = 1; i <= n; i++) scanf("%d", &fro[i].height);
        sort(fro + 1, fro + n + 1, cmp);
        sort(bac + 1, bac + n + 1, cmp);
        
        if (!work()){
            puts("impossible");
        }else{
            for (int i = 0; i < n; i++){
                printf("%d%c", ans_bac[i], i==n-1?'
':' ');
            }
            for (int i = 0; i < n; i++){
                printf("%d%c", ans_fro[i], i==n-1?'
':' ');
            }
        }
    }
    return 0;
}

kblack牛逼