Google Code Jam 2012 Round 3

Brief description:

Analysis:

有向图G 为欧拉路,当且仅当G 的基图连通,且只存在一个顶点u 的入度比出度大1、只存在一个顶点v 的入度比出度小1,其它所有顶点的入度等于出度。

const int N = 2009;

int L[N], P[N], O[N];
int n;


bool cmp(int a, int b){
    return L[a] * P[b] < L[b] * P[a];
}


int main(){

#ifdef LOCAL
    //freopen("A-small-attempt0.in", "r", stdin);
    freopen("A-large-practice.in", "r", stdin);
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    Rush{

        REP_C(i, _RD(n)) RD(L[i]);
        REP(i, n) RD(P[i]), O[i] = i;

        stable_sort(O, O+n, cmp);

        printf("Case #%d:", ++____Case);
        REP(i, n){
            printf(" %d", O[i]);
        }
        puts("");
    }
}

External link:

http://code.google.com/codejam/contest/1835486/dashboard