Zadanie "Skrzaty" z VI OIG
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Szukam pomocy

Zadanie "Skrzaty" z VI OIG

Ostatnio zmodyfikowano 2013-10-09 18:44
Autor Wiadomość
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-05 17:42:34
Czasy spadły średnio o 0.05s na dłuższych.
Chyba jednak złożoność.
P-91578
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-13 10:58:58
Mam nowy kod, po optymalizacji mieściłby się raczej w czasie, ale mam błędy.
Pomożecie?
C/C++
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>

using namespace std;

static inline void setTrue( int64_t * a, int pos )
{
    a[ pos / 64 ] |= 1 <<( pos % 64 );
}
static inline void setFalse( int64_t * a, int pos )
{
    a[ pos / 64 ] &= ~( 1 <<( pos % 64 ) );
}
static inline int getState( int64_t * a, int pos )
{
    return( a[ pos / 64 ] & 1 <<( pos % 64 ) ) >> pos % 64;
}
int main( void )
{
    int iloscSkrzatow, czasDoSnu;
    scanf( "%i", & iloscSkrzatow );
    scanf( "%i", & czasDoSnu );
    int64_t * safe = new int64_t[ iloscSkrzatow / 64 + 1 ];
    for( int a = 0; a < iloscSkrzatow / 64 + 1; a++ )
    {
        safe[ a ] = 0;
    }
    setTrue( safe, 0 );
    for( int i = 0; i < czasDoSnu; i++ )
    {
        int length;
        scanf( "%i", & length );
        int64_t * safeT = new int64_t[ iloscSkrzatow / 64 + 1 ];
        for( int b = 0; b < iloscSkrzatow / 64 + 1; b++ )
        {
            safeT[ b ] = pow(( long double ) 2, 64 ) - 1;
        }
        for( int j = 0; j < length; j++ )
        {
            int temp;
            scanf( "%i", & temp );
            setFalse( safeT, temp - 1 );
        }
        for( unsigned int m = 0; m < iloscSkrzatow; m++ )
        {
            if( getState( safe, m ) && getState( safeT, m ) )
            {
                for( unsigned int i = 0; i < iloscSkrzatow; i++ )
                if( getState( safeT, i ) )
                     setTrue( safe, i );
               
                break;
            }
        }
        if( getState( safe, iloscSkrzatow - 1 ) )
        {
            printf( "%i\n", i );
            //system("pause"); //DEBUG
            return 0;
        }
    }
    printf( "%i\n", czasDoSnu );
    //system("pause"); //DEBUG
}
VI Olimpiada Informatyczna Gimnazjalistów

Informacja o zgłoszeniu

Zadanie: skr/Skrzaty
Użytkownik: Chumanista
Rozwiązanie: skr.cpp
Data zgłoszenia: 2013-09-12 22:17:06
Status: OK
Raport

Użytkownik: Chumanista
Data: 2013-09-03 18:00:00
Wynik: 20
Komentarz: 6th Junior Polish Olympiad in Informatics, Etap II
Zadanie: skr/Skrzaty
Data: 2013-09-12 22:17:31
Wynik: 20/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 Zła odpowiedź1 0.00s/1.00s 0/20
 2b OK 0.00s/1.00s
 2c Zła odpowiedź2 0.00s/1.00s
 2d Zła odpowiedź3 0.00s/1.00s
 3a Zła odpowiedź4 0.01s/1.00s 0/20
 3b Zła odpowiedź5 0.01s/1.00s
 3c OK 0.01s/1.00s
 3d Zła odpowiedź6 0.01s/1.00s
 3e Zła odpowiedź7 0.00s/1.00s
 4a Zła odpowiedź8 0.49s/2.00s 0/20
 4b OK 0.10s/1.00s
 4c OK 0.10s/1.00s
 4d Zła odpowiedź9 0.07s/1.00s
 4e OK 4.97s/6.00s
 4f Zła odpowiedź10 0.53s/2.00s
 4g OK 0.11s/2.00s
 4h OK 0.11s/1.00s
 4i Zła odpowiedź11 0.10s/1.00s
 4j Program wywłaszczony --/3.00s
 4k Zła odpowiedź12 0.59s/2.00s
 5a Zła odpowiedź13 2.12s/4.00s 0/20
 5b Zła odpowiedź14 0.42s/3.00s
 5c OK 0.45s/4.00s
 5d Zła odpowiedź15 0.39s/3.00s
 5e Błąd wykonania16 4.99s/5.00s
 5f Zła odpowiedź17 1.92s/4.00s
 5g Zła odpowiedź18 0.36s/4.00s
 5h OK 0.44s/4.00s
 5i Zła odpowiedź19 0.42s/3.00s
 5j Błąd wykonania20 4.92s/5.00s
 5k Zła odpowiedź21 1.89s/3.00s
 5l Błąd wykonania22 4.65s/5.00s
1 wiersz 1: wczytano '30', a oczekiwano '14'
2 wiersz 1: wczytano '54', a oczekiwano '51'
3 wiersz 1: wczytano '60', a oczekiwano '40'
4 wiersz 1: wczytano '130', a oczekiwano '102'
5 wiersz 1: wczytano '251', a oczekiwano '247'
6 wiersz 1: wczytano '265', a oczekiwano '261'
7 wiersz 1: wczytano '10', a oczekiwano '0'
8 wiersz 1: wczytano '2121', a oczekiwano '2120'
9 wiersz 1: wczytano '837', a oczekiwano '798'
10 wiersz 1: wczytano '2121', a oczekiwano '2120'
11 wiersz 1: wczytano '785', a oczekiwano '784'
12 wiersz 1: wczytano '80012', a oczekiwano '80002'
13 wiersz 1: wczytano '6030', a oczekiwano '4176'
14 wiersz 1: wczytano '1578', a oczekiwano '1576'
15 wiersz 1: wczytano '1577', a oczekiwano '1573'
16 process exited due to signal 6 kod wyjścia: 1536
17 wiersz 1: wczytano '5030', a oczekiwano '3532'
18 wiersz 1: wczytano '1604', a oczekiwano '1581'
19 wiersz 1: wczytano '1623', a oczekiwano '1618'
20 process exited due to signal 6 kod wyjścia: 1536
21 wiersz 1: wczytano '160012', a oczekiwano '160002'
22 process exited due to signal 6 kod wyjścia: 1536
P-92041
DejaVu
» 2013-09-13 11:01:35
Skoro są błędy to znaczy, że algorytm masz zły lub źle go zaimplementowałeś.
P-92042
ison
» 2013-09-13 15:32:40
po optymalizacji mieściłby się raczej w czasie
Nie mieścił, nie tędy droga. Złożoność programu jest zbyt słaba. Inline'owe funkcje ani pola bitowe tu nie zdziałają cudów.
P-92057
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-14 00:23:42
A zdziałały.
Nan 80% i 2 testy w których wywala błąd którego jeszcze nie potrafię zreplikować.
Został tylko timeout w ostatnim.
kod:
C/C++
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stdint.h>

using namespace std;

static inline void setTrue( uint64_t * a, int pos )
{
    a[ pos / 64 ] |=( uint64_t ) 1 <<( pos % 64 );
}
static inline void setFalse( uint64_t * a, int pos )
{
    a[ pos / 64 ] &= ~(( uint64_t ) 1 <<( pos % 64 ) );
}
static inline int getState( uint64_t * a, int pos )
{
    return( a[ pos / 64 ] &( uint64_t ) 1 <<( pos % 64 ) ) >> pos % 64;
}
static inline void getAndSet( uint64_t * get, int pos, uint64_t * set )
{
    set[ pos / 64 ] |=( uint64_t )( get[ pos / 64 ] &( uint64_t ) 1 <<( pos % 64 ) );
}
int main( void )
{
    int iloscSkrzatow, czasDoSnu;
    scanf( "%i", & iloscSkrzatow );
    scanf( "%i", & czasDoSnu );
    uint64_t * safe = new uint64_t[ iloscSkrzatow / 64 + 1 ]();
    for( int a = 0; a < iloscSkrzatow / 64 + 1; a++ )
    {
        safe[ a ] = 0;
    }
    setTrue( safe, 0 );
    for( int i = 0; i < czasDoSnu; i++ )
    {
        int length;
        scanf( "%i", & length );
        uint64_t * safeT = new uint64_t[ iloscSkrzatow / 64 + 1 ]();
        for( int b = 0; b < iloscSkrzatow / 64 + 1; b++ )
        {
            safeT[ b ] = 18446744073709551615ll;
        }
        for( int j = 0; j < length; j++ )
        {
            int temp;
            scanf( "%i", & temp );
            setFalse( safeT, temp - 1 );
        }
        for( int m = 0; m < iloscSkrzatow; m++ )
        {
            if( getState( safe, m ) && getState( safeT, m ) )
            {
                for( int p = 0; p < iloscSkrzatow / 64 + 1; p++ )
                     safe[ p ] |= safeT[ p ];
               
                break;
            }
        }
        if( getState( safe, iloscSkrzatow - 1 ) )
        {
            printf( "%i\n", i );
            //system("pause"); //DEBUG
            return 0;
        }
    }
    printf( "%i\n", czasDoSnu );
    //system("pause"); //DEBUG
}
VI Olimpiada Informatyczna Gimnazjalistów
Informacja o zgłoszeniu
Zadanie: skr/Skrzaty
Użytkownik: Chumanista
Rozwiązanie: skr.cpp
Data zgłoszenia: 2013-09-13 21:26:10
Status: OK
Raport

Użytkownik: Chumanista
Data: 2013-09-03 18:00:00
Wynik: 80
Komentarz: 6th Junior Polish Olympiad in Informatics, Etap II
Zadanie: skr/Skrzaty
Data: 2013-09-13 21:26:30
Wynik: 80/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.01s/1.00s 20/20
 3b  OK 0.01s/1.00s
 3c  OK 0.01s/1.00s
 3d  OK 0.01s/1.00s
 3e  OK 0.00s/1.00s
 4a  OK 0.50s/2.00s 20/20
 4b  OK 0.09s/1.00s
 4c  OK 0.07s/1.00s
 4d  OK 0.11s/1.00s
 4e  OK 0.72s/6.00s
 4f  OK 0.49s/2.00s
 4g  OK 0.10s/2.00s
 4h  OK 0.10s/1.00s
 4i  OK 0.10s/1.00s
 4j  OK 0.41s/3.00s
 4k  OK 0.40s/2.00s
 5a  OK 1.47s/4.00s 0/20
 5b  OK 0.41s/3.00s
 5c  OK 0.42s/4.00s
 5d  OK 0.32s/3.00s
 5e  Błąd wykonania1 0.30s/5.00s
 5f  OK 1.31s/4.00s
 5g  OK 0.40s/4.00s
 5h  OK 0.40s/4.00s
 5i  OK 0.39s/3.00s
 5j  Błąd wykonania2 0.35s/5.00s
 5k  OK 1.28s/3.00s
 5l  Program wywłaszczony --/5.00s

1 process exited due to signal 6 kod wyjścia: 1536
2 process exited due to signal 6 kod wyjścia: 1536
P-92086
withelm
» 2013-09-15 05:51:53
Nah. Ktoś tu wspomniał, że to zadanko nie można wbić brutem(nawet bawiac sie bitami).
Tip: to zadanie trzeba roziwazac w "odwrotny" sposob niż to napisales. Nie chcesz budowac (o ile dobrze pamietam) grafu ktory ma rozmiar n^2. Btw, o ile mi sie zdaje jak sie dobrze pogógla to się znajdzie omówienia do nowszych zadan z OIG (:

Aha i tak na marginesie cały main stoi na systemie 32 bitowym, wiec uzywanie long longów jest słabe.
P-92145
Chumanista
Temat założony przez niniejszego użytkownika
» 2013-09-21 14:55:58
Serio 64bit nie ma senu?
a@ubuntu:~/Desktop$ time ./skrzaty32.out<skr5l.in
638002

real 0m2.053s
user 0m2.008s
sys 0m0.008s
a@ubuntu:~/Desktop$ time ./skrzaty64.out<skr5l.in
638002

real 0m1.370s
user 0m1.316s
sys 0m0.008s
BTW: Już nie mam timeout na ostatnim:
C/C++
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<stdint.h>

using namespace std;

static inline void setFalse( uint64_t * a, int pos )
{
    a[ pos / 64 ] &= ~(( uint64_t ) 1 <<( pos % 64 ) );
}
static inline int getState( uint64_t * a, int pos )
{
    return( a[ pos / 64 ] &( uint64_t ) 1 <<( pos % 64 ) ) >> pos % 64;
}
static inline void setTrue( uint64_t * a, int pos )
{
    a[ pos / 64 ] |=( uint64_t ) 1 <<( pos % 64 );
}

int main( void )
{
    int iloscSkrzatow, czasDoSnu;
    scanf( "%i", & iloscSkrzatow );
    scanf( "%i", & czasDoSnu );
    uint64_t * safe = new uint64_t[ iloscSkrzatow / 64 + 1 ]();
    for( int a = 0; a < iloscSkrzatow / 64 + 1; a++ )
         safe[ a ] = 0;
   
    safe[ 0 ] = 1;
    uint64_t * safeT = new uint64_t[ iloscSkrzatow / 64 + 1 ]();
    for( int i = 0; i < czasDoSnu; i++ )
    {
        memset( safeT, 255, iloscSkrzatow / 8 );
        for( int m = 0; m < iloscSkrzatow % 8; m++ )
             setTrue( safeT, iloscSkrzatow - iloscSkrzatow % 8 + m );
       
        int length;
        scanf( "%i", & length );
        for( int j = 0; j < length; j++ )
        {
            int temp;
            scanf( "%i", & temp );
            setFalse( safeT, temp - 1 );
        }
        for( int m = 0; m < iloscSkrzatow / 64 + 1; m++ )
        {
            if( safe[ m ] & safeT[ m ] )
            {
                for( int p = 0; p < iloscSkrzatow / 64 + 1; p++ )
                     safe[ p ] |= safeT[ p ];
               
                break;
            }
        }
        if( getState( safe, iloscSkrzatow - 1 ) )
        {
            printf( "%i\n", i );
            //system("pause"); //DEBUG
            return 0;
        }
        //delete[] safeT;
    }
    printf( "%i\n", czasDoSnu );
    //system("pause"); //DEBUG
}
Valgrind:
a@ubuntu:~/Desktop$ valgrind --tool=cachegrind ./skrzaty64.out  < skr5l.in
==11809== Cachegrind, a cache and branch-prediction profiler
==11809== Copyright (C) 2002-2012, and GNU GPL'd, by Nicholas Nethercote et al.
==11809== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==11809== Command: ./skrzaty64.out
==11809==
--11809-- warning: L3 cache found, using its data for the LL simulation.
638002
==11809==
==11809== I   refs:      10,654,292,679
==11809== I1  misses:             1,111
==11809== LLi misses:             1,089
==11809== I1  miss rate:           0.00%
==11809== LLi miss rate:           0.00%
==11809==
==11809== D   refs:       5,464,443,220  (4,650,042,835 rd   + 814,400,385 wr)
==11809== D1  misses:         7,638,302  (    6,350,038 rd   +   1,288,264 wr)
==11809== LLd misses:             5,330  (        4,703 rd   +         627 wr)
==11809== D1  miss rate:            0.1% (          0.1%     +         0.1%  )
==11809== LLd miss rate:            0.0% (          0.0%     +         0.0%  )
==11809==
==11809== LL refs:            7,639,413  (    6,351,149 rd   +   1,288,264 wr)
==11809== LL misses:              6,419  (        5,792 rd   +         627 wr)
==11809== LL miss rate:             0.0% (          0.0%     +         0.0%  )
a@ubuntu:~/Desktop$ cg_annotate cachegrind.out.11809  /home/a/Desktop/skrzaty64.cpp
--------------------------------------------------------------------------------
I1 cache:         32768 B, 64 B, 8-way associative
D1 cache:         32768 B, 64 B, 8-way associative
LL cache:         6291456 B, 64 B, 12-way associative
Command:          ./skrzaty64.out
Data file:        cachegrind.out.11809
Events recorded:  Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown:     Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds:       0.1 100 100 100 100 100 100 100 100
Include dirs:   
User annotated:   /home/a/Desktop/skrzaty64.cpp
Auto-annotation:  off
 
--------------------------------------------------------------------------------
            Ir  I1mr  ILmr            Dr      D1mr  DLmr          Dw      D1mw DLmw
--------------------------------------------------------------------------------
10,654,292,679 1,111 1,089 4,650,042,835 6,350,038 4,703 814,400,385 1,288,264  627  PROGRAM TOTALS
 
--------------------------------------------------------------------------------
           Ir I1mr ILmr            Dr      D1mr  DLmr          Dw    D1mw DLmw  file:function
--------------------------------------------------------------------------------
8,088,634,294   13   13 4,007,058,498 4,856,593     0  10,995,685     390  389  /home/a/Desktop/skrzaty64.cpp:main
1,250,348,057   52   52   415,553,275   161,742    73 213,763,190 638,004    0  /build/buildd/eglibc-2.17/stdio-common/vfscanf.c:_IO_vfscanf
  712,649,351    7    7     5,742,027   638,004     1 502,108,361       0    0  /build/buildd/eglibc-2.17/string/../sysdeps/i386/i686/multiarch/memset-sse2.S:__memset_sse2
  391,929,537   11   11   119,405,711    20,633     2  37,386,390  10,306    0  /build/buildd/eglibc-2.17/stdlib/strtol_l.c:____strtol_l_internal
   84,742,484    2    2    39,878,816         0     0   9,969,704       0    0  /build/buildd/eglibc-2.17/libio/genops.c:_IO_sputbackc
   49,848,520    2    2    22,431,834         0     0  19,939,408       0    0  /build/buildd/eglibc-2.17/stdlib/strtol.c:__strtol_internal
   39,878,816    2    2    12,462,130    21,995     0  17,446,982 638,002    0  /build/buildd/eglibc-2.17/stdio-common/scanf.c:scanf
   23,778,280    1    1    23,778,280         0     0           0       0    0  /build/buildd/eglibc-2.17/string/../sysdeps/i386/i686/multiarch/strcat.S:???
 
--------------------------------------------------------------------------------
-- User-annotated source: /home/a/Desktop/skrzaty64.cpp
--------------------------------------------------------------------------------
           Ir I1mr ILmr            Dr      D1mr DLmr        Dw D1mw DLmw
 
-- line 6 ----------------------------------------
            .    .    .             .         .    .         .    .    .  #include<cmath>
            .    .    .             .         .    .         .    .    .  #include<cstring>
            .    .    .             .         .    .         .    .    .  #include<stdint.h>
            .    .    .             .         .    .         .    .    . 
            .    .    .             .         .    .         .    .    .  using namespace std;
            .    .    .             .         .    .         .    .    . 
            .    .    .             .         .    .         .    .    .  static inline void setFalse(uint64_t *a, int pos)
            .    .    .             .         .    .         .    .    .  {
   44,506,104    1    1     3,708,842         0    0         0    0    0        a[pos / 64] &= ~((uint64_t) 1 << (pos % 64));
            .    .    .             .         .    .         .    .    .  }
            .    .    .             .         .    .         .    .    .  static inline int getState(uint64_t *a, int pos)
            .    .    .             .         .    .         .    .    .  {
   20,416,096    2    2     4,466,021         0    0 2,552,012    0    0        return (a[pos / 64] & (uint64_t)1 << (pos % 64)) >> pos % 64;
            .    .    .             .         .    .         .    .    .  }
            .    .    .             .         .    .         .    .    .  static inline void setTrue(uint64_t *a, int pos)
            .    .    .             .         .    .         .    .    .  {
            .    .    .             .         .    .         .    .    .        a[pos / 64] |= (uint64_t) 1 << (pos % 64);
            .    .    .             .         .    .         .    .    .  }
            .    .    .             .         .    .         .    .    . 
    2,552,013    1    1       319,001         0    0   638,003    0    0  int main(void)
            7    1    1             0         0    0         4    0    0  {
            .    .    .             .         .    .         .    .    .        int iloscSkrzatow, czasDoSnu;
            4    0    0             0         0    0         3    0    0        scanf("%i", &iloscSkrzatow);
            4    1    1             0         0    0         3    0    0        scanf("%i", &czasDoSnu);
        7,830    1    1             2         0    0     3,129  195  194        uint64_t *safe = new uint64_t[iloscSkrzatow / 64 + 1]();
        3,135    1    1             2         0    0         0    0    0        for (int a = 0; a < iloscSkrzatow / 64 + 1; a++)
        4,689    0    0             0         0    0     3,126    0    0                safe[a] = 0;
            3    0    0             1         0    0         2    0    0        safe[0] = 1;
        7,823    1    1             0         0    0     3,128  195  195        uint64_t *safeT = new uint64_t[iloscSkrzatow / 64 + 1]();
    2,552,014    0    0     1,914,008         0    0         1    0    0        for (int i = 0; i < czasDoSnu; i++)
            .    .    .             .         .    .         .    .    .        {
    2,552,012    0    0             0         0    0         0    0    0                memset(safeT,255,iloscSkrzatow / 8);
    6,380,030    1    1       638,003         0    0         0    0    0                for(int m = 0; m < iloscSkrzatow % 8; m++)
            .    .    .             .         .    .         .    .    .                        setTrue(safeT,iloscSkrzatow - iloscSkrzatow % 8 + m);
            .    .    .             .         .    .         .    .    .                int length;
    2,552,012    1    1             0         0    0 1,914,009    0    0                scanf("%i", &length);
    9,391,281    0    0     2,492,424         0    0         0    0    0                for (int j = 0; j < length; j++)
            .    .    .             .         .    .         .    .    .                {
            .    .    .             .         .    .         .    .    .                        int temp;
    7,417,684    1    1             0         0    0 5,563,263    0    0                        scanf("%i", &temp);
    1,854,421    0    0     1,854,421         0    0         0    0    0                        setFalse(safeT, temp - 1);
            .    .    .             .         .    .         .    .    .                }
1,500,585,401    0    0       957,005         0    0         0    0    0                for (int m = 0; m < iloscSkrzatow / 64 + 1; m++)
            .    .    .             .         .    .         .    .    .                {
2,995,428,773    1    1 1,996,314,511 2,734,773    0   319,002    0    0                        if (safe[m] & safeT[m])
            .    .    .             .         .    .         .    .    .                        {
1,496,114,690    0    0             0         0    0         0    0    0                                for (int p = 0; p < iloscSkrzatow / 64 + 1; p++)
1,994,394,252    0    0 1,994,394,252 2,121,820    0         0    0    0                                        safe[p] |= safeT[p];
            .    .    .             .         .    .         .    .    .                                break;
            .    .    .             .         .    .         .    .    .                        }
            .    .    .             .         .    .         .    .    .                }
    1,914,009    0    0             0         0    0         0    0    0                if (getState(safe, iloscSkrzatow - 1))
            .    .    .             .         .    .         .    .    .                {
            .    .    .             .         .    .         .    .    .                        printf("%i\n", i);
            .    .    .             .         .    .         .    .    .                        //system("pause");                              //DEBUG
            .    .    .             .         .    .         .    .    .                        return 0;
            .    .    .             .         .    .         .    .    .                }
            .    .    .             .         .    .         .    .    .                //delete[] safeT;
            .    .    .             .         .    .         .    .    .        }
            .    .    .             .         .    .         .    .    .        printf("%i\n", czasDoSnu);
            .    .    .             .         .    .         .    .    .        //system("pause");                                              //DEBUG
            7    0    0             5         0    0         0    0    0  }
            .    .    .             .         .    .         .    .    . 
 
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
--------------------------------------------------------------------------------
76    1    1 86   76    0  1    0   62  percentage of events annotated
Pomożecie?
P-92421
Admixior
» 2013-09-21 23:51:11
<< Removed by DejaVu - To, że Ty jesteś lepszym programistą nie oznacza wcale, że można używać sobie na osobach słabszych. >>

Omówienie:
Załóżmy że k jest to suma ile
Porównanie dwóch metod:
1. Twoja( z użyciem przesunięć bitowych )

Max. zużycie pamięci 1 000 000 / 64 = ~15 kB
Mieści się w 64MB więc zaliczone.

2. Metoda z użyciem odpowiedniej struktury (jeden element na każdy skrzat)

Max. zużycie pamięci tablica 1 000 000 el.
Mieści się w 64MB więc zaliczone.

Tylko teraz czy obie metody są równie dobrze? NIE! Wykonujesz wiele zbędnych rzeczy.
Porównanie jednej pętli( gdzie tutaj są 2 podobnie zdeoptymalizowane pętle)

Jak to wygląda w drugim przypadku:
1. Odczytujesz z bufora (scanf) daną.
2. Obliczas miejsce w pamięci gdzie jest ten skrzat
3. Zapisujesz w to miejsce true (odwiedzony)
KONIEC (3 kroki)

Jak wygląda to w twoim przypadku?:
1. odczytujesz z bufora scanf daną
2. odejmujesz od temp wartość 1
3. wrzucasz na stos temp-1
4. wrzucasz na stos "safeT"
5. wywołujesz funkcję setFalse
w funkcji:
6. odczytujesz pos
7. obliczasz reszte z dzielenia pos % 64 ( dzielenie długo trwa więc kompilator zamieni na & 63)
8(x2). przesuwasz bitowo jedynke o pos%64
9(x2). negujesz powyższą wartość
10. obliczasz pos/64 (dzielenie długo trwa więc kompilator zrobi przesunięcie bitowe)
11(x2). obliczasz miejsce w pamięci skrzata
12(x2). odczytujesz co tam jest (wymagane żeby zrobić and)
13(x2). robisz AND powyższej wartość z wartość w pkt. 9
14(x2). zapisujesz uzyskaną wartość pod wartość w pkt 11
15. wracasz z funkcji
16. zdejmujesz ze stosu parametry
KONIEC (16 + niektóre kroki x2 gdyż rejestry mają 32 bity a operujesz na 64)
(można tu się sprzeczać że jest inline ale nie zawsze to działa[zależy od widzimisię kompilatora podobnych zdeoptymalizowanych pętla])
Jak zauważyłeś wykonujesz wiele zbędnych rzeczy - kroków.

Jeżeli mieści się pamięciowo a algorytm będzie szybszy zawsze należy wybierać tę drogę (pamięć jest mało ważna, ważniejsza jest szybkość)

Kolejne uwagi:
1. Nie rezerwuj newem pamięci zarezerwuj ją globalnie (tablice dla max elementów) to tylko przyspieszy bo nie bawisz się w wywoływanie funkcji.

2. Jeżeli możliwe nie beaw się w zerowanie pamięć (lub przypisywanie jej odgórnie), utwórz nową wyzerowaną. Globalne są zawsze wyzerowane.

3. w pętli masz robić jak najmniej (lepiej odbić to na pamięci tworząc nową tablicę)
4. jak wymyślasz algorytm to wymyślaj tak żeby stan początkowy (w którym nie zaszło nic) to było false dlatego że globalnie tablica jest wyzerowana.
P-92443
1 « 2 » 3 4 5
Poprzednia strona Strona 2 z 5 Następna strona
» Forum » Programowanie » [C, C++] Szukam pomocy
© Wszelkie prawa zastrzeżone 2005-2024