Kirjat

/* kirjat.cpp -- Datatahti 2016 tehtava Kirjat
 *
 * Eetu "Razbit" Pesonen, 2015
 */

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

struct book
{
    int n;
    bool assigned;
    struct book* next;
};

int* uolevi;
int* maija;
int* kaaleppi;
struct book* buf;
int n; // number of books
int ndex; // first free book

struct book* next_book(struct book* book)
{
    struct book* ret = book->next;
    if (&buf[ndex] > ret)
        ret = &buf[ndex];
    while(ret && (ret->assigned != false))
        ret = ret->next;

    if (book == buf)
    {
        ndex = (&(*ret) - &(*book));
        //printf("Index: %i\n", ndex);
    }
    
    return ret;
}

// assign "book" to index i
bool assign(int i, struct book* book)
{
    //printf("Assigning %i to %i\n", book->n, i);
    
    if (uolevi[i] == book->n)
        return false;
    if (maija[i] == book->n)
        return false;
    
    kaaleppi[i] = book->n;
    book->assigned = true;

    /*for (int j = 0; j<n; j++)
    {
        printf("%i ", kaaleppi[j]);
    }
    printf("\n");*/

    if (i+1 == n)
        return true;
    
    bool ret = true;
    struct book* nx_book = buf;
    for(;;){
        if (ret == false)
        {
            nx_book = next_book(nx_book);
        }
        if (nx_book == buf && ret == true && buf->assigned == true)
        {
            nx_book = next_book(nx_book);
        }
        
        if (nx_book)
        {
            ret = assign(i+1, nx_book);
            
            if(ret)
                return true;
        }
        else
        {
            book->assigned = false;
            kaaleppi[i] = 0;
            return false;
        }
    }

    book->assigned = false;
    kaaleppi[i] = 0;
    return false;
    
}

int main()
{
    ndex = 0;
    cin >> n;

    uolevi = (int*)malloc(n*sizeof(int));
    maija = (int*)malloc(n*sizeof(int));
    kaaleppi = (int*)malloc(n*sizeof(int));
    buf = (struct book*)malloc(n*sizeof(struct book));
    
    for (int i = 0; i < n; i++)
    {
        buf[i].n = i+1;
        buf[i].assigned = false;
        buf[i].next = &buf[i+1];
        cin >> uolevi[i];
    }

    buf[n-1].next = NULL;
    
    for (int i = 0; i < n; i++)
        cin >> maija[i];
        
    struct book* first = buf;
    while(first)
    {
        if (assign(0, first))
            break;
        first = first->next;
    }

    for (int i = 0; i<n; i++)
    {
        printf("%i ", kaaleppi[i]);
    }
    printf("\n");
    
    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: ACCEPTED

Test 20

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 2

Verdict: ACCEPTED

Test 33

Group: 2

Verdict: ACCEPTED

Test 34

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 2

Verdict: ACCEPTED

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: ACCEPTED

Test 38

Group: 2

Verdict: ACCEPTED

Test 39

Group: 2

Verdict: ACCEPTED

Test 40

Group: 2

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 54

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 55

Group: 3

Verdict: ACCEPTED

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: ACCEPTED

Test 58

Group: 3

Verdict: ACCEPTED

Test 59

Group: 3

Verdict: ACCEPTED

Test 60

Group: 3

Verdict: ACCEPTED