Cod sursa(job #3217091)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 20 martie 2024 23:44:10
Problema Oras Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;

bool roy_floyd_test(vector<vector<int>> &adj) {
  int n = adj.size();
  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (i != j && adj[i][j] > 2)
        return false;

  return true;
}

void solve() {
  srand(time(NULL));
  int n, iter = 0;
  cin >> n;

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

  const int INF = 100;
  vector<vector<int>> adj(n, vector<int>(n, INF));
  while (true) {
    ++iter;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j)
        if (rand() & 1)
          adj[i][j] = 1;
        else
          adj[j][i] = 1;
    }

    if (roy_floyd_test(adj))
      break;

    for (auto &line : adj) {
      fill(line.begin(), line.end(), INF);
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j)
      if (adj[i][j] > 1 || i == j)
        cout << 0;
      else
        cout << adj[i][j];
    cout << '\n';
  }
}

int main() {
  freopen("oras.in", "r", stdin);
  freopen("oras.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}