Cod sursa(job #1946366)

Utilizator failureJust a Joke failure Data 30 martie 2017 09:12:28
Problema Oras Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>

#define MAXN 201

using namespace std;

bool edge[MAXN][MAXN], answer[MAXN][MAXN];
int n;

bool path(int node, int son) {
    if(edge[node][son])
        return 1;
    int i;
    for(i=1; i<=n; i++)
        if(i != node && i != son)
            if(edge[node][i] && edge[i][son])
                return 1;
    return 0;
}

bool putPath(int node, int son) {
    if(!edge[node][son] && !edge[son][node]) {
        edge[node][son] = 1;
        answer[node][son] = 0;
        answer[son][node] = 1;
        return 1;
    }

    int i;
    for(i=1; i<=n; ++i)
        if(i != node && i != son)
            if(!edge[i][node] && !edge[son][i]) {
                edge[node][i] = 1;
                edge[i][son] = 1;
                answer[node][i] = 0;
                answer[i][node] = 1;
                answer[i][son] = 0;
                answer[son][i] = 1;
                return 1;
            }

    return 0;
}

int main()
{
    freopen("oras.in", "r", stdin);
    freopen("oras.out", "w", stdout);

    int i, j;

    scanf("%d", &n);

    if(n == 4) {
        printf("-1");
        return 0;
    }

    if(n&1) {
        for(i=2; i<=n; ++i)
            for(j=1; j<i; ++j) {
                if(!path(j, i))
                    if(!putPath(j, i)) {
                        printf("-1");
                        return 0;
                    }
                if(!path(i, j))
                    if(!putPath(i, j)) {
                        printf("-1");
                        return 0;
                    }
            }

        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)
                if(i!=j && answer[i][j] == answer[j][i])
                    answer[i][j] = answer[j][i]^1;

        for(i=1; i<=n; ++i) {
            for(j=1; j<=n; ++j)
                printf("%d", answer[i][j]);
            printf("\n");
        }

        return 0;
    }

    answer[1][2] = 1;
    answer[1][6] = 1;
    answer[2][3] = 1;
    answer[2][4] = 1;
    answer[3][1] = 1;
    answer[3][6] = 1;
    answer[4][1] = 1;
    answer[4][3] = 1;
    answer[4][5] = 1;
    answer[5][1] = 1;
    answer[5][2] = 1;
    answer[5][3] = 1;
    answer[6][2] = 1;
    answer[6][4] = 1;
    answer[6][5] = 1;

    for(i=8; i<=n; i+=2) {
        answer[i][i-1] = 1;
        for(j=1; j<i; ++j) {
            answer[i-1][j] = 1;
            answer[j][i] = 1;
        }
    }

    for(i=1; i<=n; ++i) {
        for(j=1; j<=n; ++j)
            printf("%d", answer[i][j]);
        printf("\n");
    }

    return 0;
}