Bob wants to chase alice while alice is hard to get. If Bob wants to make a date with alice, Bob has to answer a alice's math problem firstly.
The problem is quite simple. Alice will give m constraints about an array of n positive integers representing as a[1], a[2] .. a[n]. The i-th of the m constraints consists 3 integers li, ri, qi, which means a[li] | a[li+1] | a[li+2] |...| a[ri] = qi. Here operator "|" represent as bitwise or. What Bob needs to do is to guess out the largest and smallest arrays in dictionary order which satisfy the m constraints and each element in the arrays should be positive and less than 2^30 (0
Input
The first line of input is an integer T, indicating the number of test cases. For each test case, the first line contains 2 integers: n, m (1<=n<=10^6,1<=m<=10^5). n is the size of the array, m is the number of constraints.Then follows m lines, the i-th line contains 3 integers li, ri, qi (1<=li<=ri<=n, 0<=qi<2^30) describing the i-th limit.
Output
For each cases, if answers is exists, in the first line print "come on, nice girl!"(without qoutes) then follows 2 lines, the first line contains n integers which represents the smallest array in dictionary order, and the second line conains n integers which represents the largest array in dictionary order. If answers is not exists, just print a line with a sentence "I am a poor guy!"(without qoutes)
Sample Input
2
5 2
3 4 2
1 5 3
3 2
1 3 2
1 3 3
Sample Ouput
come on, nice girl!
0 0 0 2 1
3 3 2 2 3
I am a poor guy!
http://www.acmerblog.com/hdu-3660-alice-and-bobs-trip-6621.html
#include
#include
typedef int bool;
#define true (1)
#define false (0)
typedef struct {
int array_length;
int *array_smallest;
int *array_largest;
int nbr_constraints;
int *left;
int *right;
int *quota;
} CASE;
int amax(int *a, int n) {
int i, m = a[0];
for(i=1; i<n; i++) {
if(m < a[i]) {
m = a[i];
}
}
return m;
}
void print_array(int *array, int n) {
int i;
printf("%d", array[0]);
for(i=1; i<n; i++) {
printf(" %d", array[i]);
}
printf("\n");
}
bool check(int *a, int *l, int *r, int *q, int n) {
int i, j, v;
for(i=0; i<n; i++) {
v = a[l[i]];
for(j=l[i]+1; j<=r[i]; j++) {
v |= a[j];
}
if(v != q[i]) {
return false;
}
}
return true;
}
bool iterate_order(CASE *c, int q, int d) {
if(d >= c->array_length) {
return check(c->array_smallest, c->left, c->right, c->quota, c->nbr_constraints);
}
for(c->array_smallest[d]=0; c->array_smallest[d]<=q; c->array_smallest[d]++) {
if(iterate_order(c, q, d+1)) {
return true;
}
}
return false;
}
bool iterate_inverse_order(CASE *c, int q, int d) {
if(d >= c->array_length) {
return check(c->array_largest, c->left, c->right, c->quota, c->nbr_constraints);
}
for(c->array_largest[d]=q; c->array_largest[d]>=0; c->array_largest[d]--) {
if(iterate_inverse_order(c, q, d+1)) {
return true;
}
}
return false;
}
bool validity(CASE *c) {
int i, j;
if(c->array_lengtharray_length>1000000) {
return false;
}
if(c->nbr_constraintsnbr_constraints>100000) {
return false;
}
for(i=0; inbr_constraints; i++) {
if(c->left[i]right[i]>=c->array_length || c->left[i]>c->right[i]) {
return false;
}
if(c->quota[i]quota[i]>(1< return false;
}
for(j=i+1; jnbr_constraints; j++) {
if(c->left[i]==c->left[j] && c->right[i]==c->right[j] && c->quota[i]!=c->quota[j]) {
return false;
} else if(c->left[i]<=c->left[j] && c->right[i]>=c->right[j] && c->quota[i]quota[j]) {
return false;
} else if(c->left[i]>=c->left[j] && c->right[i]<=c->right[j] && c->quota[i]>c->quota[j]) {
return false;
}
}
}
return true;
}
bool resolve(CASE *c) {
if(!validity(c)) {
return false;
}
int q = amax(c->quota, c->nbr_constraints);
return iterate_order(c, q, 0) && iterate_inverse_order(c, q, 0);
}
int main() {
int nbr_case;
CASE *cases;
int i, j;
scanf("%d", &nbr_case);
cases = (CASE *)malloc(sizeof(CASE)*nbr_case);
for(i=0; i<nbr_case; i++) {
scanf("%d %d", &cases[i].array_length, &cases[i].nbr_constraints);
cases[i].array_smallest = (int *)malloc(sizeof(int)*cases[i].array_length);
cases[i].array_largest = (int *)malloc(sizeof(int)*cases[i].array_length);
cases[i].left = (int *)malloc(sizeof(int)*cases[i].nbr_constraints);
cases[i].right = (int *)malloc(sizeof(int)*cases[i].nbr_constraints);
cases[i].quota = (int *)malloc(sizeof(int)*cases[i].nbr_constraints);
for(j=0; j<cases[i].nbr_constraints; j++) {
scanf("%d %d %d", &cases[i].left[j], &cases[i].right[j], &cases[i].quota[j]);
cases[i].left[j]--;
cases[i].right[j]--;
}
}
for(i=0; i<nbr_case; i++) {
if(resolve(&cases[i])) {
printf("come on, nice girl!\n");
print_array(cases[i].array_smallest, cases[i].array_length);
print_array(cases[i].array_largest, cases[i].array_length);
} else {
printf("I am a poor guy!\n");
}
free(cases[i].array_smallest);
free(cases[i].array_largest);
free(cases[i].left);
free(cases[i].right);
free(cases[i].quota);
}
free(cases);
return 0;
}