题意：
给出n个画的左右端点和m个钉子的位置，要求每个画上有且只有两个钉子，问最少需要放几个钉子，并输出位置。不可以的话输出i m p o s s i b l e
思路：
不可能的情况就是一个画含有的钉子数> = 3
对每个画上的钉子数进行统计，分类讨论：如果大于3的话，一定是i m p o s s i b l e；如果等于2的话，跳过；剩下的情况就要放钉子了，贪心的放，是放在r端点上。这样可以跟后面的画共用一个钉子
但是如果后面的话本身就够2个钉子了，就从r端点向前找。直到有能放的位置。
代码：
// Problem: C. Canvas Line // Contest: Codeforces - 2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019) // URL: https://codeforces.com/gym/102500/problem/C // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; struct node{ int l,r; }a[maxn]; int n,m,p[maxn]; int b[maxn]; map<int,int>mp,mp1; int main(){ n=read; rep(i,1,n){ a[i].l=read,a[i].r=read; } m=read; rep(i,1,m) p[i]=read,mp1[p[i]]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(p[j]>=a[i].l&&p[j]<=a[i].r) b[i]++; a[0].l=-100,a[0].r=-100; int j=1,flag=0; vector<int>ans; rep(i,1,n){ int l=a[i].l,r=a[i].r; int cnt=0,f=0; cnt=b[i]; if(flag&&a[i].l==a[i-1].r) cnt++; //cout<<i<<" "<<cnt<<endl; if(cnt>2){ puts("impossible");return 0; } else if(cnt!=2){ if(cnt==1){ int tmp=r; if(b[i+1]==2) tmp--; while(mp[tmp]||mp1[tmp]) tmp--; ans.push_back(tmp); mp[tmp]=1; if(tmp==r) flag=1; else flag=0; } else{ int tmp=r; if(b[i+1]==2) tmp--; while(mp[tmp]||mp1[tmp]) tmp--; ans.push_back(tmp); mp[tmp]=1; if(tmp==r) flag=1; else flag=0; while(mp[tmp]||mp1[tmp]) tmp--; ans.push_back(tmp); mp[tmp]=1; } } if(mp[r]) flag=1; else flag=0; } cout<<ans.size()<<endl; for(auto it:ans) cout<<it<<" "; return 0; }
