题目描述
ICPC manager plans a new project which is to be carried out for n days. In this project, m persons numbered from 1 to m are supposed to work. Each day j (1 ≤ j ≤ n) requires dj persons, and each person i (1 ≤ i ≤ m) wants to work wi days.
To increase the efficiency in performing the project, the following two conditions should be satisfied:
1.each person works for only consecutive w days when he/she works, and
2.each person can work again after he/she has a rest for at least h days.
ICPC manager wants to find a working plan to assign the working days for all persons such that the number of working days of each person i (1 ≤ i ≤ m) is equal to wi and the number of persons who work for each day j (1 ≤ j ≤ n) is equal to dj, and above two conditions are also satisfied.
For example, assume the project is carried out for n = 9 days, and m = 4 persons participate in the project. Let w = 2 and h = 1. Also, assume (w1, w2, w3, w4) = (4, 4, 6, 2) and (d1, d2, d3, d4, d5, d6, d7, d8, d9) = (1, 3, 2, 1, 2, 1, 1, 3, 2). The table below shows a feasible solution where the i-th row corresponds to person i, and the j-th column corresponds to day j. If person i works or has a rest in day j, the value of the table element with row i and column j is 1 or 0, respectively.
Given m, n, w, h, wi (1 ≤ i ≤ m) which is a multiple of w, and dj (1 ≤ j ≤ n), write a program to find a feasible solution as a working plan.
输入
Your program is to read from standard input. The input starts with a line containing four integers, m, n, w, h (1 ≤ m ≤ 2,000, 1 ≤ n ≤ 2,000, 1 ≤ w, h ≤ n). The following line contains m integers where the i-th (1 ≤ i ≤ m) integer represents wi (1 ≤ wi ≤ n) which is a multiple of w. The next line contains n integers where the j-th (1 ≤ j ≤ n) integer represents dj (0 ≤ dj ≤ m).
输出
Your program is to write to standard output. If there is a feasible working plan, print 1 in the first line followed by m lines, each i-th (1 ≤ i ≤ m) line should contain wi/w integers. These integers form an increasing sequence of first days that person i works in the feasible plan. If there is no feasible working plan, print only -1 in the first line. The first sample below corresponds to the example given in the table above.
样例输入
复制样例数据
4 9 2 1
4 4 6 2
1 3 2 1 2 1 1 3 2
样例输出
1
1 8
2 7
2 5 8
4
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e3+50;
#define lowbit(x) x&(-x)
inline int read()
{
int 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;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
ll qmod(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a)%mod;
}
b>>=1;
a=(a*a)%mod;
}
return ans;
}
ll inv(ll a)
{
return qmod(a,mod-2);
}
struct node
{
int id,st,ed,workday;
node() {}
node( int id,int st,int ed,int workday): id(id),st(st),ed(ed),workday(workday) {}
bool operator < (const node &other) const
{
if(st!=other.st)
{
return st>other.st;
}
return workday<other.workday;
}
};
bool cmp(node a,node b)
{
return a.workday<b.workday;
}
int n,m,w,h;
int work[maxn],d[maxn];
priority_queue<node>q;
priority_queue<int, vector<int>, greater<int> >Day;
vector<int> ans[maxn];
node stac[maxn];
int top;
void init()
{
while(!q.empty())
{
q.pop();
}
while(!Day.empty())
{
Day.pop();
}
for(int i=1; i<=m; i++)
{
ans[i].clear();
}
}
int main()
{
while(scanf("%d %d %d %d",&m,&n,&w,&h)!=EOF)
{
init();
for(int i=1; i<=m; i++)
{
scanf("%d",&work[i]);
}
for(int i=1; i<=n; i++)
{
scanf("%d",&d[i]);
}
for(int i=1; i<=m; i++)
{
q.push(node(i,0,0,work[i]));
}
bool flag=true;
int cnt=0;
top=0;
for(int i=1; i<=n; i++)
{
while(!Day.empty())
{
if(Day.top()<i)
{
Day.pop();
}
else
{
break;
}
}
int daysize=Day.size();
if(daysize>d[i])
{
flag=false;
break;
}
if(d[i]==daysize)
{
continue;
}
while(!q.empty())
{
if(q.top().st<=i)
{
stac[++top]=q.top();
q.pop();
}
else
{
break;
}
}
sort(stac+1,stac+1+top,cmp);
while(Day.size()<d[i])
{
if(top<1)
{
flag=false;
break;
}
node tmp=stac[top--];
tmp.st=i;
ans[tmp.id].push_back(i);
tmp.st+=w;
Day.push(tmp.st-1);
tmp.st+=h;
tmp.workday-=min(w,n-i+1);
if(tmp.workday)
{
q.push(tmp);
}
else
{
cnt++;
}
}
if(Day.size()!=d[i])
{
flag=false;
}
if(!flag)
{
break;
}
}
if(cnt!=m)
{
flag=false;
}
if(flag)
{
puts("1");
for(int i=1; i<=m; i++)
{
for(int j=0,len=ans[i].size(); j<len-1; j++)
{
printf("%d ",ans[i][j]);
}
printf("%d\n",ans[i][ans[i].size()-1]);
}
}
else
{
puts("-1");
}
}
return 0;
}