Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Zadanie "Skrzaty" z VI OIG

Ostatnio zmodyfikowano 2013-10-09 18:44
Autor Wiadomość
Chumanista
Temat założony przez niniejszego użytkownika
Zadanie "Skrzaty" z VI OIG
» 2013-09-04 19:05:42
Witam.
Napisałem coś takiego jako rozwiązanie
http://main.edu.pl/pl/archive​/oig/6/skr

C/C++
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>

using namespace std;

bool contains( vector < int > v, int x )
{
    if( std::find( v.begin(), v.end(), x ) != v.end() )
         return true;
    else
         return false;
   
}
vector < int > vadd( vector < int > a, vector < int > b )
{
    vector < int > out( a );
    for( unsigned int i = 0; i < b.size(); i++ )
    if( !( contains( out, b[ i ] ) ) )
         out.push_back( b[ i ] );
   
    return out;
}
int main( void )
{
    int iloscSkrzatow, czasDoSnu;
    scanf( "%i", & iloscSkrzatow );
    scanf( "%i", & czasDoSnu );
    vector < int > safe;
    safe.push_back( 1 );
    for( int i = 0; i < czasDoSnu; i++ )
    {
        int length;
        scanf( "%i", & length );
        vector < int > unsafe;
        vector < int > safeT;
        for( int j = 0; j < length; j++ )
        {
            int temp;
            scanf( "%i", & temp );
            unsafe.push_back( temp );
        }
        for( int k = 1; k < iloscSkrzatow + 1; k++ )
        if( !( contains( unsafe, k ) ) )
             safeT.push_back( k );
       
        for( unsigned int m = 0; m < safeT.size(); m++ )
        {
            int var = safeT[ m ];
            if( contains( safe, var ) )
            {
                safe = vadd( safe, safeT );
                break;
            }
        }
        if( contains( safe, iloscSkrzatow ) )
        {
            printf( "%i\n", i );
            return 0;
        }
    }
    printf( "%i\n", czasDoSnu );
}

Ale niestety wyniki nie są najlepsze:

Informacja o zgłoszeniu
Zadanie:         skr/Skrzaty
Użytkownik:         Chumanista
Rozwiązanie:         skr.cpp
Data zgłoszenia: 2013-09-04 18:35:35
Status:         OK
Raport

Użytkownik:    Chumanista
Data:         2013-09-03 18:00:00
Wynik:         60
Komentarz: 6th Junior Polish Olympiad in Informatics, Etap II
Zadanie: skr/Skrzaty
Data:         2013-09-04 18:36:26
Wynik:  60/100
Pliki:  rozwiązanie

 Test Wynik           Czas/Limit Punkty
 0   OK                 0.00s/1.00s 0/0
 0b  OK                 0.00s/1.00s 0/0
 0c  OK                 0.00s/1.00s 0/0
 1a  OK                 0.00s/1.00s 20/20
 1b  OK                 0.00s/1.00s
 2a  OK                 0.00s/1.00s 20/20
 2b  OK                 0.00s/1.00s
 2c  OK                 0.00s/1.00s
 2d  OK                 0.00s/1.00s
 3a  OK                 0.04s/1.00s 20/20
 3b  OK                 0.04s/1.00s
 3c  OK                 0.04s/1.00s
 3d  OK                 0.03s/1.00s
 3e  OK                 0.00s/1.00s
 4a  Program wywłaszczony --/2.00s 0/20
 4b  OK                 0.47s/1.00s
 4c  OK                 0.98s/1.00s
 4d  OK                 0.46s/1.00s
 4e  Program wywłaszczony --/6.00s
 4f  Program wywłaszczony --/2.00s
 4g  OK                 0.46s/2.00s
 4h  OK                 0.95s/1.00s
 4i  OK                 0.45s/1.00s
 4j  Program wywłaszczony --/3.00s
 4k  Program wywłaszczony --/2.00s
 5a  Program wywłaszczony --/4.00s 0/20
 5b  OK                 2.77s/3.00s
 5c  Program wywłaszczony --/4.00s
 5d  OK                 2.70s/3.00s
 5e  Program wywłaszczony --/5.00s
 5f  Program wywłaszczony --/4.00s
 5g  OK                 2.78s/4.00s
 5h  Program wywłaszczony --/4.00s
 5i  OK                 2.80s/3.00s
 5j  Program wywłaszczony --/5.00s
 5k  Program wywłaszczony --/3.00s
 5l  Błąd wykonania 1   2.77s/5.00s

1 process exited due to signal 9 kod wyjścia: 2304
Pomożecie zoptymalizować?
P-91544
pekfos
» 2013-09-04 22:24:00
Po co ciągle tworzysz i kopiujesz wektory?
P-91549
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-05 06:37:50
Byłoby lepiej?
C/C++
vector < int > vadd( vector < int > a, vector < int > b )
{
    for( unsigned int i = 0; i < b.size(); i++ )
    if( !( contains( a, b[ i ] ) ) )
         out.push_back( b[ i ] );
   
    return a;
}
P-91552
DejaVu
» 2013-09-05 08:34:22
Poczytaj o referencjach.
Frazy, które należy wpisać w wyszukiwarkę google:
http://cpp0x.pl/kursy/Kurs-C++​/Poziom-3​/Przekazywanie-argumentow-funk​cji-przez-referencje​/356
P-91553
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-05 16:29:37
Dziękuję bardzo, czasy spadły o połowę, ale to wciąż za dużo:
C/C++
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>

using namespace std;

bool contains( vector < int > & v, int x )
{
    if( std::find( v.begin(), v.end(), x ) != v.end() )
         return true;
    else
         return false;
   
}
void vadd( vector < int > & a, vector < int > & b )
{
    for( unsigned int i = 0; i < b.size(); i++ )
    if( !( contains( a, b[ i ] ) ) )
         a.push_back( b[ i ] );
   
}
int main( void )
{
    int iloscSkrzatow, czasDoSnu;
    scanf( "%i", & iloscSkrzatow );
    scanf( "%i", & czasDoSnu );
    vector < int > safe;
    safe.push_back( 1 );
    for( int i = 0; i < czasDoSnu; i++ )
    {
        int length;
        scanf( "%i", & length );
        vector < int > unsafe;
        vector < int > safeT;
        for( int j = 0; j < length; j++ )
        {
            int temp;
            scanf( "%i", & temp );
            unsafe.push_back( temp );
        }
        for( int k = 1; k < iloscSkrzatow + 1; k++ )
        if( !( contains( unsafe, k ) ) )
             safeT.push_back( k );
       
        for( unsigned int m = 0; m < safeT.size(); m++ )
        {
            int var = safeT[ m ];
            if( contains( safe, var ) )
            {
                vadd( safe, safeT );
                break;
            }
        }
        if( contains( safe, iloscSkrzatow ) )
        {
            printf( "%i\n", i );
            //system("pause"); //DEBUG
            return 0;
        }
    }
    printf( "%i\n", czasDoSnu );
    //system("pause"); //DEBUG
}
Informacja o zgłoszeniu
Zadanie: skr/Skrzaty
Użytkownik: janr/Jan Równicki
Rozwiązanie: skr.cpp
Data zgłoszenia: 2013-09-05 16:25:41
Status: OK
Raport

Użytkownik: Jan Równicki (janr)
Data: 2013-09-03 18:00:00
Wynik: 60
Komentarz: 6th Junior Polish Olympiad in Informatics, Etap II
Zadanie: skr/Skrzaty
Data: 2013-09-05 16:26:14
Wynik: 60/100
Pliki: rozwiązanie

Test Wynik Czas/Limit Punkty
 0  OK 0.00s/1.00s 0/0
 0b  OK 0.00s/1.00s 0/0
 0c  OK 0.00s/1.00s 0/0
 1a  OK 0.00s/1.00s 20/20
 1b  OK 0.00s/1.00s
 2a  OK 0.00s/1.00s 20/20
 2b  OK 0.00s/1.00s
 2c  OK 0.00s/1.00s
 2d  OK 0.00s/1.00s
 3a  OK 0.02s/1.00s 20/20
 3b  OK 0.01s/1.00s
 3c  OK 0.02s/1.00s
 3d  OK 0.02s/1.00s
 3e  OK 0.00s/1.00s
 4a  Program wywłaszczony --/2.00s 0/20
 4b  OK 0.24s/1.00s
 4c  OK 0.39s/1.00s
 4d  OK 0.20s/1.00s
 4e  Program wywłaszczony --/6.00s
 4f  Program wywłaszczony --/2.00s
 4g  OK 0.22s/2.00s
 4h  OK 0.36s/1.00s
 4i  OK 0.22s/1.00s
 4j  Program wywłaszczony --/3.00s
 4k  Program wywłaszczony --/2.00s
 5a  Program wywłaszczony --/4.00s 0/20
 5b  OK 1.31s/3.00s
 5c  OK 2.54s/4.00s
 5d  OK 1.22s/3.00s
 5e  Program wywłaszczony --/5.00s
 5f  Program wywłaszczony --/4.00s
 5g  OK 1.28s/4.00s
 5h  OK 2.55s/4.00s
 5i  OK 1.29s/3.00s
 5j  Program wywłaszczony --/5.00s
 5k  Program wywłaszczony --/3.00s
 5l  Program wywłaszczony --/5.00s
P-91565
pekfos
» 2013-09-05 16:35:17
Nie twórz wektorów w pętli.
P-91566
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-05 16:54:13
No to jak?
Stworzyć poza i czyścić w pętli?
P-91573
DejaVu
» 2013-09-05 17:36:01
C/C++
vector < int > unsafe;
vector < int > safeT;
unsafe.reserve( length );
safeT.reserve( length );

/edit:
Poza tym być może algorytm ma zbyt dużą złożoność w stosunku do oczekiwanego i dlatego masz wywłaszczenia.
P-91577
« 1 » 2 3 4 5
  Strona 1 z 5 Następna strona