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#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ć? |
|
pekfos |
» 2013-09-04 22:24:00 Po co ciągle tworzysz i kopiujesz wektory? |
|
Chumanista Temat założony przez niniejszego użytkownika |
» 2013-09-05 06:37:50 Byłoby lepiej? 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; }
|
|
DejaVu |
» 2013-09-05 08:34:22 |
|
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: #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 ); return 0; } } printf( "%i\n", czasDoSnu ); } 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 |
|
pekfos |
» 2013-09-05 16:35:17 Nie twórz wektorów w pętli. |
|
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? |
|
DejaVu |
» 2013-09-05 17:36:01 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. |
|
« 1 » 2 3 4 5 |