Cod sursa(job #2324019)

Utilizator rares.amarandeiRares Amarandei rares.amarandei Data 20 ianuarie 2019 10:24:07
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <stdlib.h>
#include <stdint.h>
#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <memory>
#include <algorithm>
#include <deque>
#include <iterator>
#include <numeric>
#include <assert.h>
#include <cstdlib>
#include <sstream>
#include <fstream>

#define INPUT_PATH ""
#define OUTPUT_PATH ""

void algorithm();

int main()
{
  algorithm();
  return 0;
}
using namespace std;

namespace
{
////////////////////////////////////////////////////////////////////////////////
vector<int> fillRowSums(
  const vector<int>&  matrix, 
  const int           nrRows,
  const int           nrCols)
{
  vector<int> rowSums(nrRows, 0);
  for (int row = 0; row < nrRows; ++row)
  {
    int rowSum = 0;
    for (int col = 0; col < nrCols; ++col)
    {
      rowSum += matrix[row*nrCols + col];
    }
    rowSums[row] = rowSum;
  }
  return rowSums;
}

////////////////////////////////////////////////////////////////////////////////
vector<int> fillColSums(
  const vector<int>&  matrix,
  const int           nrRows,
  const int           nrCols)
{
  vector<int> colSums(nrCols, 0);
  for (int col = 0; col < nrCols; ++col)
  {
    int colSum = 0;
    for (int row = 0; row < nrRows; ++row)
    {
      colSum += matrix[row*nrCols + col];
    }
    colSums[col] = colSum;
  }
  return colSums;
}

////////////////////////////////////////////////////////////////////////////////
void flipRow(
  vector<int>&  matrix, 
  const int     rowToFlip,
  const int     nrRows,
  const int     nrCols)
{
  for (int col = 0; col < nrCols; ++col)
  {
    matrix[rowToFlip*nrCols + col] *= -1;
  }
}

////////////////////////////////////////////////////////////////////////////////
void flipCol(
  vector<int>&  matrix,
  const int     colToFlip,
  const int     nrRows,
  const int     nrCols)
{
  for (int row = 0; row < nrRows; ++row)
  {
    matrix[row*nrCols + colToFlip] *= -1;
  }
}
}

////////////////////////////////////////////////////////////////////////////////
void algorithm()
{
  ifstream inputFile(INPUT_PATH "flip.in");
  ofstream outputFile(OUTPUT_PATH "flip.out");

  int nrRows = 0; inputFile >> nrRows;
  int nrCols = 0; inputFile >> nrCols;

  vector<int> matrix; 
  matrix.reserve(nrRows*nrCols);

  int readVal = 0;
  while (inputFile >> readVal)
  {
    matrix.push_back(readVal);
  }

  int sum = accumulate(matrix.begin(), matrix.end(), 0);
  int sumBeforeFlip = sum - 1;
  while (sum > sumBeforeFlip)
  {
    sumBeforeFlip = sum;
    vector<int> rowSums = fillRowSums(matrix, nrRows, nrCols);
    vector<int> colSums = fillColSums(matrix, nrRows, nrCols);
    vector<int>::iterator itMinRow = min_element(begin(rowSums), end(rowSums));
    vector<int>::iterator itMinCol = min_element(begin(colSums), end(colSums));
    if (*itMinRow < *itMinCol)
    {
      flipRow(matrix, itMinRow - begin(rowSums), nrRows, nrCols);
    }
    else
    {
      flipCol(matrix, itMinCol - begin(colSums), nrRows, nrCols);
    }
    sum = accumulate(matrix.begin(), matrix.end(), 0);
  }
  
  outputFile << sumBeforeFlip;
  inputFile.close();
  outputFile.close();
}