INPUT
1 2
1
0
1
1 0
1 0
OUTPUT
0
is correct?

Both your tests are invalid. Two officials cannot share one weekday. "So there may work not more than one official at the same time."

Test 5 - "No Solution"

well, #5 is 'No Solution'
stuck with #7

can someone advise on this code?

i put tests somewhere with 'puts(NULL)' so if the thing i expect happens, i will get 'ACCESS VIOLATION' there.

the method is to just get the closest document done as possible until all is finished. if no document can be done in the weekday length period, there is no solution.

in this version in input line by line so if there is any garbage at the end of a line, it is ignored.

i dont see any other problems though.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#include <sstream>

using namespace std;

const int Inf = 1000000000;
//const int Inf = 1000000;

char buf[4096];

int main (void) {
    int n, l;
    gets(buf);
    sscanf(buf, "%d %d", &n, &l);
    if (n < 1 || n > 100) puts(NULL);
    if (l < n || l > 100) puts(NULL);
    int w[128] = {0};
    gets(buf);
    istringstream is0(buf);
    for (int i = 1, j; i <= n; ++ i) {
//        scanf("%d", &j);
        if (!(is0 >> j)) puts(NULL);
        if (j < 1 || j > l) puts(NULL);
//        if (w[j]) puts(NULL);
        w[j] = i;
    }
    bool d[102][102] = {{false}};
    int nd[128] = {0};
    for (int i = 1, j; i <= n; ++ i) {
        gets(buf);
        istringstream is(buf);
        while (is >> j && j) {
//        while (1 == scanf("%d", &j) && j) {
            if (!d[i][j]) {
                d[i][j] = true;
                ++ nd[i];
            }
            else puts(NULL);
        }
    }
    int now;
    gets(buf);
    sscanf(buf, "%d", &now);
    if (now < 1 || now > l) puts(NULL);
    bool having[128] = {false}, need[128] = {false};
    gets(buf);
    istringstream is1(buf);
    for (int i; is1 >> i && i; having[i] = true);
    gets(buf);
    istringstream is2(buf);
    for (int i; is2 >> i && i; need[i] = true);

    for (int i = 1; i <= n; ++ i) {
        if (having[i]) {
// testing if a document he has is also required, no failure yet till test #7
//            if (need[i]) puts(NULL);
//            need[i] = false;
            for (int j = 1; j <= n; ++ j) {
                if (d[j][i]) {
                    d[j][i] = false;
                    -- nd[j];
                }
            }
        }
        else need[i] = true;   // the missing documents are all needed
    }

    int rest = 0;
    for (int i = 1; i <= n; ++ i) {
// the following line fail on test #4, thus there are missing documents in test #4
//        if (having[i] == need[i]) puts(NULL);
        if (need[i]) ++ rest;
    }

    int days = 0, seq[128], k = 0;
    -- days;
    -- now;
    while (rest && days < Inf) {
        bool nothing = true;
//        while (days < Inf) {
        for (int i = l; i >= 0; -- i) {
            ++ now;
            ++ days;
            if (now > l) now = 1;
            int x;
            if ((x = w[now]) && 0 == nd[x] && need[x]) {
                -- rest;
                need[x] = false;
                for (int i = 1; i <= n; ++ i) {
                    if (d[i][x]) {
                        d[i][x] = false;
                        -- nd[i];
                    }
                }
                seq[k ++] = x;
                nothing = false;
                break;
            }
        }
        if (nothing) days = Inf;
    }

    if (days < Inf) {
        if (days < 0) days = 0;
        printf("%d\n", days);
        if (k) {
            for (int i = 0; i < k; ++ i) {
                if (i) putchar(' ');
                printf("%d", seq[i]);
            }
            putchar('\n');
        }
    }
    else {
//        puts(NULL);
        puts("No Solution");
    }

    return 0;
}


Edited by author 25.10.2004 06:30

Edited by author 25.10.2004 06:34

Your test helped me to find my own bug (though it was WA5). Thanks! :)