Submission #120819

#	Time	Username	Problem	Language	Result	Execution time	Memory
120819		cvele	Sajam (COCI18_sajam)	C++14	90 / 90	214 ms	2460 KiB

sajam

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

struct open {
  int x, on, t;
  open(int x, int on, int t) : x(x), on(on), t(t) {}
};

struct cmp {
  bool operator()(const open &a, const open &b) {
    if (a.on != b.on) {
      return a.on > b.on;
    }
    if (a.t != b.t) {
      return a.t < b.t;
    }
    if (a.x < b.x) {
      return a.x < b.x;
    }
    return 0;
  }
};

set <open, cmp> s;

int main() {
  int n, k;
  cin >> n >> k;
  char mat[n][n];
  int row[n], col[n];
  for (int i = 0; i < n; i++) {
    cin >> mat[i];
  }
  for (int i = 0; i < n; i++) {
    int on = 0;
    for (int j = 0; j < n; j++) {
      on += mat[i][j] == 'o';
    }
    row[i] = on;
    s.insert(open(i, on, 0));
  }
  for (int j = 0; j < n; j++) {
    int on = 0;
    for (int i = 0; i < n; i++) {
      on += (mat[i][j] == 'o');
    }
    col[j] = on;
    s.insert(open(j, on, 1));
  }
  bool usedrow[n], usedcol[n];
  memset(usedcol, 0, sizeof usedcol);
  memset(usedrow, 0, sizeof usedrow);
  while (!s.empty()) {
    open here = *s.begin(); s.erase(s.begin());
    if (here.t == 0) {
      usedrow[here.x] = 1;
    } else {
      usedcol[here.x] = 1;
    }
    if (here.on >= n - here.on) {
      if (here.t == 0) {
        int x = here.x;
        for (int y = 0; y < n; y++) {
          if (!usedcol[y]) {
            s.erase(open(y, col[y], 1));
            if (mat[x][y] == 'x') col[y]++;
            else col[y]--;
            s.insert(open(y, col[y], 1));
          }
          if (mat[x][y] == 'x') mat[x][y] = 'o';
          else mat[x][y] = 'x';
        }
      } else {
        int y = here.x;
        for (int x = 0; x < n; x++) {
          if (!usedrow[x]) {
            s.erase(open(x, row[x], 0));
            if (mat[x][y] == 'x') row[x]++;
            else row[x]--;
            s.insert(open(x, row[x], 0));
          }
          if (mat[x][y] == 'x') mat[x][y] = 'o';
          else mat[x][y] = 'x';
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans += (mat[i][j] == 'o');
    }
  }
  if (ans <= k) {
    cout << "DA" << endl;
  } else {
    cout << "NE" << endl;
  }
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15