CSES - Datatähti 2016 alku - Results
Submission details
Task:Osajono
Sender:Razbit
Submission time:2015-09-29 21:29:03
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.05 s1details
#20.05 s1details
#30.05 s1details
#40.05 s1details
#50.06 s1details
#60.06 s2details
#70.06 s2details
#80.05 s2details
#90.05 s2details
#100.05 s2details
#110.06 s3details
#120.05 s3details
#130.05 s3details
#140.05 s3details
#150.06 s3details

Code

/* 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 details

Test 1

Group: 1

Verdict:

input
BBBAABBBAAAABBAAAABAABAABBBBBB...

correct output
2554

user output
(empty)

Test 2

Group: 1

Verdict:

input
GDFVYWQCZAFGICSXOSWBZMGPDBSSVL...

correct output
299

user output
(empty)

Test 3

Group: 1

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAZAAAA...

correct output
4314

user output
(empty)

Test 4

Group: 1

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
4231

user output
(empty)

Test 5

Group: 1

Verdict:

input
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
5050

user output
(empty)

Test 6

Group: 2

Verdict:

input
BBABABBBABBAABBABBABAABAAABABA...

correct output
6253029

user output
(empty)

Test 7

Group: 2

Verdict:

input
RBKJMLDVQMKHYKCNDIVVKOMFUXTFMG...

correct output
485173

user output
(empty)

Test 8

Group: 2

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
12427725

user output
(empty)

Test 9

Group: 2

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
12467549

user output
(empty)

Test 10

Group: 2

Verdict:

input
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
12502500

user output
(empty)

Test 11

Group: 3

Verdict:

input
BAAAAABABBABAABAABABABBBABBAAB...

correct output
2500051369

user output
(empty)

Test 12

Group: 3

Verdict:

input
ABBURXDRVXAYBPXXOQZNYHLWGUEEWR...

correct output
192407124

user output
(empty)

Test 13

Group: 3

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
4998050400

user output
(empty)

Test 14

Group: 3

Verdict:

input
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

correct output
4998850144

user output
(empty)

Test 15

Group: 3

Verdict:

input
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
5000050000

user output
(empty)