Cod sursa(job #2034414)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 octombrie 2017 19:40:36
Problema Oras Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

const string IN = "oras.in";
const string OUT = "oras.out";
vector<pair<int, int>>p;
int dir[203][203], sol[203][20];

int res[203][203];
bool valid(int n) {
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(i != j && !dir[i][j]) {
                bool any = 0;

                for(int k = 0; k < n; ++k) if(dir[i][k] == 1 && dir[k][j] == 1) any = 1;

                if(!any) return 0 ;
            }
        }
    }

    return 1;
}
void gen(int n) {
    for(int i = 0; i < n; ++i)for(int j = i + 1; j < n; ++j)p.emplace_back(i, j);

    for(int c = 0; c < 1 << p.size(); ++c) {

        for(int j = 0; j < p.size(); ++j) {
            int a = p[j].first, b = p[j].second;

            if((1 << j)&c) {
                dir[a][b] = 1;
                dir[b][a] = 0;
            } else {
                dir[a][b] = 0;
                dir[b][a] = 1;
            }
        }

        if(valid(n)) {
            for(int j = 0; j < n; ++j)for(int k = 0; k < n; ++k)sol[j][k] = dir[j][k], res[j][k] = sol[j][k];

            return;
        }
    }

}
int start;
void adaug() {
    for(int i = 0; i < start; ++i) {
        res[i][start + 1] = '1';
        res[start + 1][i] = '0';
    }

    res[start + 1][start + 2] = '1';
    res[start + 2][start + 1] = '0';

    for(int i = 0; i < start; ++i) {

        res[i][start + 2] = '0';
        res[start + 2][i] = '1';
    }

}
int main() {
    ifstream cin(IN);
    ofstream cout(OUT);

    int n;
    cin >> n;

    if(n == 4) {
        cout << -1;
        return 0;
    }

   start = 4;

    if(n % 2 == 0) {
        gen(4), start = 4;
    } else gen(3), start = 3;

    while(start < n) {
        adaug();
        start += 2;
    }

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(res[i][j] && i != j)cout << 1;
            else cout << 0;
        }

        cout << '\n';
    }

}