Benelux Algorithm Programming Contest 2019 H. Historic Exhibition（思维）

The Benelux Artistic Pottery Consortium is preparing for an exhibit of its most prized urns and vases at a gallery in Nijmegen. Due to the sheer number of vases to be put on display the gallery has trouble finding a pedestal of the right size for every single vase. They have pedestals available that can either be placed normally or upside down and can be characterised by the diameter of their top and bottom surface. Moreover, the diameter of the top and bottom varies by at most one unit length.For artistic reasons, it is important that the diameter of the base of a vase matches the diameter of the surface of the pedestal it is placed on. You have been asked to find a way to place all the vases on available pedestals. In order to make this work, you might need to turn some of the pedestals upside down. For example, Figure H.1 shows a possible assignment of pedestals to vases for sample input 1. Assist the gallery by writing a program to compute such an assignment.

input

The first line contains two integers 0 \le p, v \le 10^40≤p,v≤104 the number of pedestals and the number of vases.Then follow p lines, the i_{th}ith of which contains two integers 1 \le a_i, b_i \le 10^41≤ai,bi≤104 denoting the diameters of the different sides of pedestal i. It is given that \vert a_i-b_i\vert \le 1∣ai−bi∣≤1.Then follows a single line containing v integers 1 \le c_1, c_2, ..., c_v \le 10^41≤c1,c2,...,cv≤104, where ci denotes the diameter of vase i.

output

Output v distinct integers 1 \le x_1, x_2, ... x_v \le p1≤x1,x2,...xv≤p such that vase i can stand on pedestal x_ixi, or print impossible if no assignment of vases to pedestals exists.If there are multiple possible solutions, you may output any one of them.

本题答案不唯一，符合要求的答案均正确

样例输入1复制

样例输出1复制

1
4
3

样例输入2复制

样例输出2复制

impossible

样例输入3复制

样例输出3复制

impossible

题意：

将花瓶与其大小相同的底座配对，底座可以倒置，给出花瓶底的大小和底座上下底的大小，底座的两个底大小最多差1。

思路：

使用unordered_map<int, stack<int> >mp1, mp2; 将上底与下底相同的底座的下标存入mp1中，将上底与下底不同的底座按较小的大小存入mp2中。再将花瓶按大小排序，对于每个花瓶大小 w ，先查询 w 是否在mp1中，否的话查询 w - 1 是否在mp2中（因为花瓶是从小到大排序的，若较大底都不满足条件，这个底座就没有用了），否的话再查询 w 是否在mp2中，都不在的话impossible。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;

int ans[N];

struct node
{
    int id, w;
}s[N];

bool cmp(node x, node y)
{
    return x.w < y.w;
}

int main()
{
    int p, v, aa, bb;
    while(~scanf("%d%d", &p, &v))
    {
        unordered_map<int, stack<int> >mp1;
        unordered_map<int, stack<int> >mp2;
        for(int i = 1; i <= p; ++i)
        {
            scanf("%d%d", &aa, &bb);
            if(aa > bb)
                swap(aa, bb);
            if(aa == bb)
            {
                mp1[aa].push(i);
            }
            else
            {
                mp2[aa].push(i);
            }
        }
        for(int i = 1; i <= v; ++i)
        {
            scanf("%d", &s[i].w);
            s[i].id = i;
        }
        sort(s + 1, s + v + 1, cmp);
        bool flag = 1;
        for(int i = 1; i <= v; ++i)
        {
            if(mp1[s[i].w].size())
            {
                ans[s[i].id] = mp1[s[i].w].top();
                mp1[s[i].w].pop();
            }
            else if(mp2[s[i].w - 1].size())
            {
                ans[s[i].id] = mp2[s[i].w - 1].top();
                mp2[s[i].w - 1].pop();
            }
            else if(mp2[s[i].w].size())
            {
                ans[s[i].id] = mp2[s[i].w].top();
                mp2[s[i].w].pop();
            }
            else
            {
                flag = 0;
                break;
            }
        }
        if(!flag)
        {
            cout<<"impossible"<<'\n';
        }
        else
        {
            for(int i = 1; i <= v; ++i)
            {
                cout<<ans[i]<<'\n';
            }
        }
    }
    return 0;
}