pdp forum

Το επίσημο forum του ΠΔΠ
https://www.pdpforum.eu.org/forum/

24th - 2nd Round Solutions

https://www.pdpforum.eu.org/forum/viewtopic.php?f=8&t=2249

Σελίδα 1 από 1

24th - 2nd Round Solutions

Δημοσιεύτηκε: Τετ Μαρ 07, 2012 2:56 pm
από mariosal
pulsars: https://github.com/mariosal/algo/blob/m ... /pulsars.c

Κώδικας: Επιλογή όλων

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

typedef struct {
    unsigned short x, y;
    int id;
} point;

point min;

int cross( point a, point b, point c ) {
    return ( int )( b.x - a.x ) * ( c.y - a.y ) - ( b.y - a.y ) * ( c.x - a.x );
}
unsigned distance2( point a, point b ) {
    return ( unsigned )( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y );
}

int pCompare( const void *a, const void *b ) {
    int wise;
    unsigned d, d2;

    wise = cross( min, *( point* )a, *( point* )b );
    if ( wise > 0 ) {
        return -1;
    }
    if ( wise < 0 ) {
        return 1;
    }

    d = distance2( min, *( point* )a );
    d2 = distance2( min, *( point* )b );
    if ( d < d2 ) {
        return -1;
    }
    return 1;
}
int hCompare( const void *a, const void *b ) {
    return ( ( point* )a )->id - ( ( point* )b )->id;
}

int main() {
    int n, m, i;
    point *p, *hull;

    freopen( "pulsars.in", "r", stdin );
    freopen( "pulsars.out", "w", stdout );

    scanf( "%d", &n );
    p = ( point* )malloc( n * sizeof( point ) );
    hull = ( point* )malloc( n * sizeof( point ) );

    for ( i = 0; i < n; i += 1 ) {
        scanf( "%hu %hu", &p[ i ].x, &p[ i ].y );
        p[ i ].id = i + 1;

        if ( !i || min.y > p[ i ].y || ( min.y == p[ i ].y && min.x > p[ i ].x ) ) {
            min = p[ i ];
        }
    }

    qsort( p, n, sizeof( point ), pCompare );
    m = 0;
    for ( i = 0; i < n; i += 1 ) {
        while ( m >= 2 && cross( hull[ m - 2 ], hull[ m - 1 ], p[ i ] ) <= 0 ) {
            m -= 1;
        }

        hull[ m ] = p[ i ];
        m += 1;
    }

    qsort( hull, m, sizeof( point ), hCompare );
    printf( "%d\n", m );
    for ( i = 0; i < m; i += 1 ) {
        printf( "%d\n", hull[ i ].id );
    }

    return 0;
}
operators: https://github.com/mariosal/algo/blob/m ... perators.c

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int n, i, j, min[ 2 ], *a;

    freopen( "operators.in", "r", stdin );
    freopen( "operators.out", "w", stdout );

    scanf( "%d", &n );
    a = ( int* )malloc( n * sizeof( int ) );

    for ( i = 0; i < n; i += 1 ) {
        scanf( "%d", &a[ i ] );
    }

    i = 0;
    j = n - 1;
    min[ 0 ] = a[ i ];
    min[ 1 ] = a[ j ];
    while ( i < j ) {
        if ( abs( min[ 0 ] + min[ 1 ] ) > abs( a[ i ] + a[ j ] ) ) {
            min[ 0 ] = a[ i ];
            min[ 1 ] = a[ j ];
            if ( a[ i ] + a[ j ] == 0 ) {
                break;
            }
        }
        if ( a[ i ] + a[ j ] > 0 ) {
            j -= 1;
        }
        else {
            i += 1;
        }
    }

    printf( "%d %d\n", min[ 0 ], min[ 1 ] );

    return 0;
}

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Τετ Μαρ 07, 2012 3:28 pm
από infinity
operators:
[pastebin]http://pastebin.com/4EYpJ3uW[/pastebin]

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Τετ Μαρ 07, 2012 4:49 pm
από kernelpanic
Spoiler: show
[pastebin]http://pastebin.com/Sw6HViAZ[/pastebin]
Οι πιθανές τιμές των χ,y είναι 40001.
Από τα σημεία που βρίσκονται σε μια οποιαδήποτε ευθεία, μόνο τα 2 ακραία είναι δυνατό να ανήκουν στο πολύγωνο-τα εσωτερικά περικλείονται.
Επομένως, το πολύ 80.000 σημεία ανήκουν στο πολύγωνο.
Από'κει και πέρα ένας αλγόριθμος Ο(Ν2) πιάνει αρκετές μονάδες ;)

Εδώ, ο Ο(Ν) αλγόριθμος με τη βοήθεια μιας στοίβας και του εξωτερικού γινομένου βρίσκει μια γραμμή που αρχίζει στο ελάχιστο χ, τελειώνει εκεί που είναι μέγιστο, και στρέφει tequila προς τα πάνω, και μια γραμμή που αρχίζει στο ελάχιστο χ, τελειώνει εκεί που είναι μέγιστο, και στρέφει tequila προς τα κάτω, ενώ τα πιθανά σημεία περιέχονται στο πολύγωνο που αυτές οι δύο σχηματίζουν.

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Τετ Μαρ 07, 2012 5:53 pm
από themis5
Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Παρ Μαρ 09, 2012 9:33 pm
από infinity
themis5 έγραψε:Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}
φίλε θέμη για Ν=1000000 τα φτύνει λίγο

infinity@netbook-debian:~/Desktop$ time ./pulsars

real 0m6.961s
user 0m6.848s
sys 0m0.088s

μπορεί στους υπολογιστές της hellenico να είναι λιγότερο, αλλά εδώ το έχασες λίγο :P

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Σάβ Μαρ 10, 2012 2:29 am
από karantias
Να πω την αλήθεια έχω χάσει τη λύση που είχα υποβάλλει, ελπίζω να μπορέσω να την δω κάποια στιγμή από το hellenico.

Αυτή η λύση είναι παρόμοια, modification της λύσης μου για το bsheep.

Κώδικας: Επιλογή όλων

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

typedef struct {
    int x, y;
    unsigned int id;
} point;

point M;

long long ccw( point A, point B, point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

unsigned int dist( point A, point B ) {
    return ( B.x - A.x ) * ( B.x - A.x ) + ( B.y - A.y ) * ( B.y - A.y );
}

int cmpolar( const void *a, const void *b ) {
    point aa = *( point* )a;
    point bb = *( point* )b;
    unsigned int dist1, dist2; //else overflow for N=10^6
    long long angle = ccw( M, aa, bb );
    if ( angle > 0 ) {
        return -1;
    }
    if ( angle < 0 ) {
        return 1;
    }

    //angle == 0: points collinear
    dist1 = dist( M, aa );
    dist2 = dist( M, bb );
    if ( dist1 < dist2 ) {
        return -1;
    }
    if ( dist1 > dist2 ) {
        return 1;
    }

    //resort to id comparison
    return cmpid( a, b );
}
int cmpid( const void *a, const void *b ) {
    return ( ( point* )a )->id - ( ( point* )b )->id;
}

int main( void ) {
    FILE *fin = fopen( "pulsars.txt", "r" );
    FILE *fout = fopen( "pulsars.out", "w" );
    unsigned int N, i, hn = 0;
    point *Q, *H;

    //N points
    fscanf( fin, "%u", &N );
    Q = ( point* )malloc( N * sizeof( point ) );
    H = ( point* )malloc( N * sizeof( point ) );


    //scan each point
    for ( i = 0; i < N; ++i ) {
        fscanf( fin, "%d %d", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].id = i + 1;
    }

    //find minimum
    M = Q[ 0 ];
    for ( i = 1; i < N; ++i ) {
        if ( Q[ i ].y < M.y || ( Q[ i ].y == M.y && Q[ i ].x < M.x ) ) {
            M = Q[ i ];
        }
    }

    //sort by polar angle
    qsort( Q, N, sizeof( point ), cmpolar );

    //create the convex hull
    //points >= 10 so we put in the first 3 anyway
    i = 0;
    H[ hn++ ] = Q[ i++ ];
    H[ hn++ ] = Q[ i++ ];
    H[ hn++ ] = Q[ i++ ];
    for ( i = i; i < N; ++i ) {
        if ( i && Q[ i - 1 ].x == Q[ i ].x && Q[ i - 1 ].y == Q[ i ].y ) {
            continue;
        }
        while ( hn >= 2 && ccw( H[ hn - 2 ], H[ hn - 1 ], Q[ i ] ) <= 0 ) {
            --hn;
        }
        H[ hn++ ] = Q[ i ];
    }

    //sort by id
    qsort( H, hn, sizeof( point ), cmpid );

    //print out the hull points
    fprintf( fout, "%d\n", hn );
    for ( i = 0; i < hn; ++i ) {
        fprintf( fout, "%u\n", H[ i ].id );
    }

    free( Q );
    free( H );

    return 0;
}

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Σάβ Μαρ 10, 2012 2:41 am
από themis5
infinity έγραψε:
themis5 έγραψε:Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}
φίλε θέμη για Ν=1000000 τα φτύνει λίγο

infinity@netbook-debian:~/Desktop$ time ./pulsars

real 0m6.961s
user 0m6.848s
sys 0m0.088s

μπορεί στους υπολογιστές της hellenico να είναι λιγότερο, αλλά εδώ το έχασες λίγο :P
Για το testcase του Σωτήρη το οποίο έχει το ίδιο μέγεθος:
Berners:pulsars themicp$ time ./pulsars

real 0m0.525s
user 0m0.507s
sys 0m0.016s

Εσύ σε ποιο το τρέχεις;

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Σάβ Μαρ 10, 2012 3:42 pm
από infinity
themis5 έγραψε:
infinity έγραψε:
themis5 έγραψε:Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}
φίλε θέμη για Ν=1000000 τα φτύνει λίγο

infinity@netbook-debian:~/Desktop$ time ./pulsars

real 0m6.961s
user 0m6.848s
sys 0m0.088s

μπορεί στους υπολογιστές της hellenico να είναι λιγότερο, αλλά εδώ το έχασες λίγο :P
Για το testcase του Σωτήρη το οποίο έχει το ίδιο μέγεθος:
Berners:pulsars themicp$ time ./pulsars

real 0m0.525s
user 0m0.507s
sys 0m0.016s

Εσύ σε ποιο το τρέχεις;
Στου σωτήρη, απλως το τρέχω απο netbook οπότε παίζει να φταίει και αυτο λίγο (ως πολύ) :P

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Δευ Μαρ 12, 2012 3:35 pm
από feedWARd
infinity έγραψε:operators:
[pastebin]http://pastebin.com/4EYpJ3uW[/pastebin]
Πολύ καλή λύση! Κάποιες μικρές παρατηρήσεις:
1. Αν θες να βάλεις έλεγχο στην scanf το καλύτερο που έχεις να κάνεις είναι να βλέπεις αν διάβασες τόσα ορίσματα όσα περίμενες, π.χ. scanf("%d %d", &a, &b) == 2. Στην συγκεκριμένη περίπτωση δεν έχει διαφορά, αλλά γενικά είναι καλή πρακτική.
2. Ποιος ο λόγος να χρησιμοποιήσεις fabs αντί για abs;
3. To σημαντικότερο: αφού το neg ουστιαστικά είναι μια στοίβα, είναι πολύ καλύτερο να χρησιμοποιήσεις την δομή stack της stl.Δες τι κάνει η push_back στο vector.

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Δευ Μαρ 12, 2012 6:57 pm
από infinity
feedWARd έγραψε:
infinity έγραψε:operators:
[pastebin]http://pastebin.com/4EYpJ3uW[/pastebin]
Πολύ καλή λύση! Κάποιες μικρές παρατηρήσεις:
1. Αν θες να βάλεις έλεγχο στην scanf το καλύτερο που έχεις να κάνεις είναι να βλέπεις αν διάβασες τόσα ορίσματα όσα περίμενες, π.χ. scanf("%d %d", &a, &b) == 2. Στην συγκεκριμένη περίπτωση δεν έχει διαφορά, αλλά γενικά είναι καλή πρακτική.
2. Ποιος ο λόγος να χρησιμοποιήσεις fabs αντί για abs;
3. To σημαντικότερο: αφού το neg ουστιαστικά είναι μια στοίβα, είναι πολύ καλύτερο να χρησιμοποιήσεις την δομή stack της stl.Δες τι κάνει η push_back στο vector.
1. βασικά, δεν είναι τόσο για έλεγχο της scanf όσο το ότι προσπαθούσα να μειώσω όσο το δυνατόν περισσότερο τις γραμμές κώδικα (ναι έχω ένα κόλλημα με αυτό :P)
2. Κανένας ουσιαστικός λόγος, απλώς τη fabs χρησιμοποιούσα ανέκαθεν :P.
3. Ναι, απλώς επειδή δεν γνωρίζω και πολύ καλα την stl χρησιμοποίησα vector, για να κρατήσω τις αρνητικές τιμές, που είναι το data structure που ξέρω καλύτερα...

ευχαριστώ για τα καλά σου λόγια, αλλά και για τις συμβουλές...

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Δευ Μαρ 12, 2012 8:29 pm
από feedWARd
infinity έγραψε: 1. βασικά, δεν είναι τόσο για έλεγχο της scanf όσο το ότι προσπαθούσα να μειώσω όσο το δυνατόν περισσότερο τις γραμμές κώδικα (ναι έχω ένα κόλλημα με αυτό :P)
Τότε απλά scanf(...) && ....
infinity έγραψε: 3. Ναι, απλώς επειδή δεν γνωρίζω και πολύ καλα την stl χρησιμοποίησα vector, για να κρατήσω τις αρνητικές τιμές, που είναι το data structure που ξέρω καλύτερα...
Οκ, απλα πρόσεξε οτι η push_back είναι O(N) στο vector.

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Δευ Μαρ 19, 2012 9:11 pm
από kostantinaras
Και η δικιά μου:
[pastebin]http://pastebin.com/qyYyYkrT[/pastebin]
Ξέρω οτι είναι ολίγον ο,τι νάνε! :?

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Τρί Μαρ 20, 2012 12:19 am
από mariosal
kostantinaras έγραψε:[pastebin]http://pastebin.com/qyYyYkrT[/pastebin]
Εικόνα

https://xkcd.com/292/

Re: 24th - 2nd Round Solutions

Δημοσιεύτηκε: Τρί Μαρ 20, 2012 4:19 pm
από infinity
Ναι όντως γιατι τόσα goto @konstantinaras? :P
Όλοι οι χρόνοι είναι UTC+03:00
Σελίδα 1 από 1

Δημιουργήθηκε από phpBB® Forum Software © phpBB Limited


Ελληνική μετάφραση από το phpbbgr.com